Permutation-partition pairs: a combinatorial generalization of graph embeddings

Author:
Saul Stahl

Journal:
Trans. Amer. Math. Soc. **259** (1980), 129-145

MSC:
Primary 05C10

DOI:
https://doi.org/10.1090/S0002-9947-1980-0561828-2

Erratum:
Trans. Amer. Math. Soc. **266** (1981), 333.

MathSciNet review:
561828

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Permutation-partition pairs are a purely combinatorial generalization of graph embeddings. Some parameters are defined here for these pairs and several theorems are proved. These results are strong enough to prove virtually all the known theoretical informaton about the genus parameter as well as a new theorem regarding the genus of the amalgamation of two graphs over three points.

**[A1]**S. R. Alpert,*The genera of amalgamations of graphs*, Trans. Amer. Math. Soc.**78**(1973), 1-39. MR**0371698 (51:7915)****[A2]**-,*The genera of edge amalgamations of complete bigraphs*(in preparation).**[BC]**M. Behzad and G. Chartrand,*Introduction to the theory of graphs*, Allyn and Bacon, Boston, Mass., 1971. MR**0432461 (55:5449)****[BHKY]**J. Battle, F. Harary, Y. Kodama and J. W. T. Youngs,*Additivity of the genus of a graph*, Bull. Amer. Math. Soc.**68**(1962), 565-568. MR**0155313 (27:5247)****[C]**A. Cayley,*On the colouring of maps*, Proc. London Math. Soc.**9**(1878), 148.**[DGH]**R. W. Decker, H. H. Glover and J. P. Huneke,*The genus of*2-*connected graphs*(in preparation).**[HK]**F. Harary and Y. Kodama,*On the genus of an n-connected graph*, Fund. Math.**54**(1964), 7-13. MR**0161331 (28:4539)****[H1]**P. J. Heawood,*Map colour theorem*, Quart. J. Math.**24**(1890), 332-338.**[H2]**D. Husemoller,*Ramified coverings of Riemann surfaces*, Duke Math. J.**29**(1962), 167-174. MR**0136726 (25:188)****[LR]**C. Little and R. Ringeisen,*An additivity theorem for maximum genus of a graph*, Discrete Math.**21**(1978), 69-74. MR**523420 (80d:05022)****[NRSW]**E. A. Nordhaus, R. D. Ringeisen, B. M. Stewart and A. T. White,*A Kuratowski type theorem for the maximum genus of a graph*, J. Combinatorial Theory Ser. B**12**(1972), 260-267. MR**0299523 (45:8571)****[R]**G. Ringel,*Map color theorem*, Springer-Verlag, Berlin and New York, 1974. MR**0349461 (50:1955)****[S]**S. Stahl,*A counting theorem for topological graph theory*, Theory and Application of Graphs (Proc. Conf. Western Michigan Univ., Kalamazoo, Mich., 1976), Y. Alavi and D. R. Lick (eds.), Lecture Notes in Math., vol. 642, Springer-Verlag, Berlin and New York, 1976, pp. 534-544. MR**0505728 (58:21750)****[W]**T. R. S. Walsh,*Hypermaps versus bipartite maps*, J. Combinatorial Theory Ser. B**18**(1975), 155-163. MR**0360328 (50:12778)**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
05C10

Retrieve articles in all journals with MSC: 05C10

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1980-0561828-2

Article copyright:
© Copyright 1980
American Mathematical Society