Permutationpartition pairs: a combinatorial generalization of graph embeddings
Author:
Saul Stahl
Journal:
Trans. Amer. Math. Soc. 259 (1980), 129145
MSC:
Primary 05C10
Erratum:
Trans. Amer. Math. Soc. 266 (1981), 333.
MathSciNet review:
561828
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Permutationpartition 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]
Seth
R. Alpert, The genera of amalgamations of
graphs, Trans. Amer. Math. Soc. 178 (1973), 1–39. MR 0371698
(51 #7915), http://dx.doi.org/10.1090/S0002994719730371698X
 [A2]
, The genera of edge amalgamations of complete bigraphs (in preparation).
 [BC]
Mehdi
Behzad and Gary
Chartrand, Introduction to the theory of graphs, Allyn and
Bacon Inc., Boston, Mass., 1971. MR 0432461
(55 #5449)
 [BHKY]
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 0155313
(27 #5247), http://dx.doi.org/10.1090/S000299041962108477
 [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 2connected graphs (in preparation).
 [HK]
F.
Harary and Y.
Kodama, On the genus of an 𝑛connected graph, Fund.
Math. 54 (1964), 7–13. MR 0161331
(28 #4539)
 [H1]
P. J. Heawood, Map colour theorem, Quart. J. Math. 24 (1890), 332338.
 [H2]
Dale
H. Husemoller, Ramified coverings of Riemann surfaces, Duke
Math. J. 29 (1962), 167–174. MR 0136726
(25 #188)
 [LR]
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 (80d:05022), http://dx.doi.org/10.1016/0012365X(78)901486
 [NRSW]
E.
A. Nordhaus, R.
D. Ringeisen, B.
M. Stewart, and A.
T. White, A Kuratowskitype theorem for the maximum genus of a
graph, J. Combinatorial Theory Ser. B 12 (1972),
260–267. MR 0299523
(45 #8571)
 [R]
Gerhard
Ringel, Map color theorem, SpringerVerlag, New
YorkHeidelberg, 1974. Die Grundlehren der mathematischen Wissenschaften,
Band 209. MR
0349461 (50 #1955)
 [S]
Saul
Stahl, A counting theorem for topological graph theory, Theory
and applications of graphs (Proc. Internat. Conf., Western Mich. Univ.,
Kalamazoo, Mich., 1976) Springer, Berlin, 1978, pp. 534–544.
Lecture Notes in Math., Vol. 642. 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)
 [A1]
 S. R. Alpert, The genera of amalgamations of graphs, Trans. Amer. Math. Soc. 78 (1973), 139. 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), 565568. 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 2connected graphs (in preparation).
 [HK]
 F. Harary and Y. Kodama, On the genus of an nconnected graph, Fund. Math. 54 (1964), 713. MR 0161331 (28:4539)
 [H1]
 P. J. Heawood, Map colour theorem, Quart. J. Math. 24 (1890), 332338.
 [H2]
 D. Husemoller, Ramified coverings of Riemann surfaces, Duke Math. J. 29 (1962), 167174. MR 0136726 (25:188)
 [LR]
 C. Little and R. Ringeisen, An additivity theorem for maximum genus of a graph, Discrete Math. 21 (1978), 6974. 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), 260267. MR 0299523 (45:8571)
 [R]
 G. Ringel, Map color theorem, SpringerVerlag, 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, SpringerVerlag, Berlin and New York, 1976, pp. 534544. MR 0505728 (58:21750)
 [W]
 T. R. S. Walsh, Hypermaps versus bipartite maps, J. Combinatorial Theory Ser. B 18 (1975), 155163. MR 0360328 (50:12778)
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC:
05C10
Retrieve articles in all journals
with MSC:
05C10
Additional Information
DOI:
http://dx.doi.org/10.1090/S00029947198005618282
PII:
S 00029947(1980)05618282
Article copyright:
© Copyright 1980
American Mathematical Society
