Edge-Maximal Graphs on Surfaces

McDiarmid, Colin ; Wood, David R.

Canadian journal of mathematics, Tome 70 (2018) no. 4, pp. 925-942

Résumé

We prove that for every surface $\Sigma $ of Euler genus $g$ , every edge-maximal embedding of a graph in $\Sigma $ is at most $O(g)$ edges short of a triangulation of $\Sigma $ . This provides the first answer to an open problem of Kainen (1974).

Détail

DOI : 10.4153/CJM-2017-028-0

Mots-clés : 05C10, graph, surface, embedding

Bibliographie

[1] [1] Archdeacon, D., The nonorientable genus is additive. J. Graph Theory 10(1986), 363–383. Google Scholar | DOI

[2] [2] Harary, F., Kainen, P. C., Schwenk, A. J., and White, A. T., A maximal toroidal graph which is not a triangulation. Math. Scand. 33(1973), 108–112. http://dx.doi.Org/10.7146/math.scand.a-11476 Google Scholar

[3] [3] Joret, G. and Wood, D. R., Irreducible triangulations are small. J. Combin. Theory Ser. B 100(2010), no. 5, 446–455. http://dx.doi.Org/10.1016/j.jctb.2010.01.004 Google Scholar

[4] [4] Kainen, P. C., Some recent results in topological graph theory. In: Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington D.C., 1973), Lecture Notes in Math., 406, Springer, Berlin, 1974, pp. 76–108. Google Scholar

[5] [5] Kostochka, A. V., Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica 4(1984), no. 4, 307–316. Google Scholar | DOI

[6] [6] McDiarmid, C. and Przykucki, M., On the purity of minor-closed classes of graphs. 2016. arxiv:1 608.08623 Google Scholar

[7] [7] Miller, G. L., An additivity theorem for the genus of a graph. J. Combin. Theory Ser. B 43(1987), no. 1, 25–47. Google Scholar | DOI

[8] [8] Mohar, B. and Thomassen, C., Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2001. Google Scholar

[9] [9] Nakamoto, A. and Ota, K., Note on irreducible triangulations of surfaces. J. Graph Theory 20(1995), 227–233. Google Scholar | DOI

[10] [10] Richter, R. B., On the Euler genus of a 2-connected graph. J. Combin. Theory Ser. B 43(1987), 60–69. Google Scholar | DOI

[11] [11] Ringel, G., Das Geschlecht des vollstaändigen paaren Graphen. Abh. Math. Sem. Univ. Hamburg 28(1965, 139–150. Google Scholar | DOI

[12] [12] Ringel, G., Der vollstaändige paare Graph auf nichtorientierbaren Flächen. J. Reine Angew. Math. 220(1965), 88–93. http://dx.doi.Org/10.1515/crll.1965.220.88 Google Scholar

[13] [13] Thomason, A., An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc. 95(1984), 261–265. Google Scholar | DOI

[14] [14] Thomason, A., The extremal function for complete minors. J. Combin. Theory Ser. B 81(2001), 318–338. http://dx.doi.Org/10.1006/jctb.2000.2013 Google Scholar

[15] [15] Thomassen, C., Embeddings of graphs with no short noncontractible cycles. J. Combin. Theory Ser. B 48(1990), 155–177. Google Scholar | DOI

[16] [16] Wagner, K., Über eine Eigenschaft der ebene Komplexe. Math. Ann. 114(1937), 570–590. Google Scholar | DOI