Geodesic
The maximum genus, matchings and the cycle space of a graph
Czechoslovak Mathematical Journal, Tome 48 (1998) no. 2, pp. 329-339 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

In this paper we determine the maximum genus of a graph by using the matching number of the intersection graph of a basis of its cycle space. Our result is a common generalization of a theorem of Glukhov and a theorem of Nebeský .
In this paper we determine the maximum genus of a graph by using the matching number of the intersection graph of a basis of its cycle space. Our result is a common generalization of a theorem of Glukhov and a theorem of Nebeský .
Classification : 05C10, 05C38, 05C70
Keywords: Maximum genus; matching; cycle space 
@article{CMJ_1998_48_2_a9,
     author = {Fu, Hung-Lin and \v{S}koviera, Martin and Tsai, Ming-Chun},
     title = {The maximum genus, matchings and the cycle space of a graph},
     journal = {Czechoslovak Mathematical Journal},
     pages = {329--339},
     year = {1998},
     volume = {48},
     number = {2},
     mrnumber = {1624256},
     zbl = {0949.05015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_1998_48_2_a9/}
}
TY  - JOUR
AU  - Fu, Hung-Lin
AU  - Škoviera, Martin
AU  - Tsai, Ming-Chun
TI  - The maximum genus, matchings and the cycle space of a graph
JO  - Czechoslovak Mathematical Journal
PY  - 1998
SP  - 329
EP  - 339
VL  - 48
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_1998_48_2_a9/
LA  - en
ID  - CMJ_1998_48_2_a9
ER  - 
%0 Journal Article
%A Fu, Hung-Lin
%A Škoviera, Martin
%A Tsai, Ming-Chun
%T The maximum genus, matchings and the cycle space of a graph
%J Czechoslovak Mathematical Journal
%D 1998
%P 329-339
%V 48
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_1998_48_2_a9/
%G en
%F CMJ_1998_48_2_a9
Fu, Hung-Lin; Škoviera, Martin; Tsai, Ming-Chun. The maximum genus, matchings and the cycle space of a graph. Czechoslovak Mathematical Journal, Tome 48 (1998) no. 2, pp. 329-339. http://geodesic.mathdoc.fr/item/CMJ_1998_48_2_a9/

[1] C. Berge: Sur le couplage maximum d’un graphe. C. R. Acad. Sci. Paris (A) 247 (1958), 258–259. | MR | Zbl

[2] C. P. Bonnington: The relative maximum genus of a graph. J. Combin. Theory Ser. B 60 (1994), 195–206. | DOI | MR | Zbl

[3] G. Chartrand, A. D. Polimeni and M. J. Stewart: The existence of $1$-factors in line graphs, squares, and total graphs. Indag. Math. 35 (1973), 228–232. | DOI | MR

[4] J. Chen and J. Gross: Kuratowski-type theorems for average genus. J. Combin. Theory Ser. B 57 (1993), 100–121. | DOI | MR

[5] A. D. Glukhov: The maximum genus of planar graphs. Ukrain. Mat. Zh. 34 (1982), 97–99. (Russian) | MR

[6] J. L. Gross and R. G. Rieper: Local extrema in genus-stratified graphs. J. Graph Theory 15 (1991), 159–171. | DOI | MR

[7] P. Hall: On representation of subsets. J. London Math. Soc. 10 (1935), 26–30. | DOI

[8] M. Jungerman: A characterization of upper embeddable graphs. Trans. Amer. Math. Soc. 241 (1978), 401–406. | MR | Zbl

[9] N. P. Khomenko and A. D. Glukhov: Single-component $2$-cell embeddings and the maximum genus of a graph. Some Topological and Combinatorial Properties of Graphs, Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1980, pp. 5–23. (Russian) | MR

[10] N. P. Khomenko, N. A. Ostroverkhy and V. A.Kuzmenko: The maximum genus of a graph. $\varphi $-Transformations of Graphs, Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1973, pp. 180–207. (Ukrainian, English summary)

[11] N. P. Khomenko and E. V. Yavorsky: $\varphi $-Transformations of the representation graph. Preprint 70.7, Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1970. (Russian) | MR

[12] D. König: Graphok és matrixok. Math. Fiz. Lapok 38 (1931), 116–119. (Hungarian)

[13] L. Nebeský: A new characterization of the maximum genus of a graph. Czechoslovak Math. J. 31 (106) (1981), 604–613. | MR

[14] L. Nebeský: On $2$-cell embeddings of graphs with minimum number of regions. Czechoslovak Math. J. 35 (110) (1985), 625–631. | MR

[15] L. Nebeský: Characterizing the maximum genus of a connected graph. Czechoslovak Math. J. 43 (118) (1993), 177–185. | MR

[16] E. A. Nordhaus, B. M. Stewart and A. T. White: On the maximum genus of a graph. J. Combin. Theory Ser. B 11 (1971), 258–267. | DOI | MR

[17] 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. Combin. Theory Ser. B 12 (1972), 260–267. | DOI | MR

[18] J. Širáň and M. Škoviera: Characterization of the maximum genus of a signed graph. J. Combin. Theory Ser. B 52 (1991), 124–146. | DOI | MR

[19] D. P. Sumner: Graphs with $1$-factors. Proc. Amer. Math. Soc. 42 (1974), 8–12. | MR | Zbl

[20] W. T. Tutte: The factorization of linear graphs. J. London Math. Soc. 22 (1947), 107–111. | MR | Zbl

[21] N. H. Xuong: How to determine the maximum genus of a graph. J. Combin. Theory Ser. B (1979), 217–225. | MR | Zbl

[22] T. Zaslavsky: Orientation embedding of signed graphs. J. Graph Theory 16 (1992), 399–422. | DOI | MR | Zbl