Permutation-partition pairs: a combinatorial generalization of graph embeddings

Stahl, Saul

doi:10.1090/S0002-9947-1980-0561828-2

Permutation-partition pairs: a combinatorial generalization of graph embeddings
HTML articles powered by AMS MathViewer

by Saul Stahl PDF

Trans. Amer. Math. Soc. 259 (1980), 129-145 Request permission

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

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.

References

Seth R. Alpert, The genera of amalgamations of graphs, Trans. Amer. Math. Soc. 178 (1973), 1–39. MR 371698, DOI 10.1090/S0002-9947-1973-0371698-X

The genera of edge amalgamations of complete bigraphs

Mehdi Behzad and Gary Chartrand, Introduction to the theory of graphs, Allyn and Bacon, Inc., Boston, Mass., 1971. MR 0432461
Joseph Battle, Frank Harary, Yukihiro Kodama, and J. W. T. Youngs, Additivity of the genus of a graph, Bull. Amer. Math. Soc. 68 (1962), 565–568. MR 155313, DOI 10.1090/S0002-9904-1962-10847-7

On the colouring of maps

9

The genus of

connected graphs

F. Harary and Y. Kodama, On the genus of an $n$-connected graph, Fund. Math. 54 (1964), 7–13. MR 161331, DOI 10.4064/fm-54-1-7-13

Map colour theorem

24

Dale H. Husemoller, Ramified coverings of Riemann surfaces, Duke Math. J. 29 (1962), 167–174. MR 136726
C. H. C. Little and R. D. Ringeisen, An additivity theorem for maximum genus of a graph, Discrete Math. 21 (1978), no. 1, 69–74. MR 523420, DOI 10.1016/0012-365X(78)90148-6
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 299523, DOI 10.1016/0095-8956(72)90040-8
Gerhard Ringel, Map color theorem, Die Grundlehren der mathematischen Wissenschaften, Band 209, Springer-Verlag, New York-Heidelberg, 1974. MR 0349461
Saul Stahl, A counting theorem for topological graph theory, Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976) Lecture Notes in Math., Vol. 642, Springer, Berlin, 1978, pp. 534–544. MR 0505728
T. R. S. Walsh, Hypermaps versus bipartite maps, J. Combinatorial Theory Ser. B 18 (1975), 155–163. MR 360328, DOI 10.1016/0095-8956(75)90042-8