×

An extension of Kotzig’s theorem. (English) Zbl 1350.05026

Summary: A. Kotzig [“Contribution to the theory of Eulerian polyhedra”, Mat.-Fyz. Čas., Slovensk. Akad. Vied 5, 101–113 (1955)] proved that every 3-connected planar graph has an edge with the degree sum of its end vertices at most 13, which is tight. An edge \(uv\) is of type \((i, j)\) if \(d(u)\leq i\) and \(d(v)\leq j\). O. V. Borodin [Diskretn. Mat. 3, No. 4, 24–27 (1991; Zbl 0742.05034)] proved that every normal plane map contains an edge of one of the types (3, 10), (4, 7), or (5, 6), which is tight. R. Cole et al. [SIAM J. Discrete Math. 21, No. 1, 93–106 (2007; Zbl 1138.05059)] deduced from this result by Borodin that Kotzig’s bound of 13 is valid for all planar graphs with minimum degree \(\delta\) at least 2 in which every \(d\)-vertex, \(d\geq 12\), has at most \(d-11\) neighbors of degree 2.
We give a common extension of the three above results by proving for any integer \(t\geq1\) that every plane graph with \(\delta\geq2\) and no \(d\)-vertex, \(d\geq11+t\), having more than \(d-11\) neighbors of degree 2 has an edge of one of the following types: (2, 10+t), (3, 10), (4, 7), or (5, 6), where all parameters are tight.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] V.A. Aksenov, O.V. Borodin, L.S. Mel’nikov, G. Sabidussi, M. Stiebitz and B. Toft, Deeply asymmetric planar graphs, J. Combin. Theory Ser. B 95 (2005) 68-78. doi:; · Zbl 1070.05031 · doi:10.1016/j.jctb.2005.03.002
[2] S.V. Avgustinovich and O.V. Borodin, Neighborhoods of edges in normal maps, Diskretn. Anal. Issled. Oper. 2 (1995) 3-9, in Russian.; · Zbl 0856.05031
[3] O.V. Borodin, On the total coloring of planar graphs, J. Reine Angew. Math. 394 (1989) 180-185.; · Zbl 0653.05029
[4] O.V. Borodin, Joint generalization of the theorems of Lebesgue and Kotzig on the combinatorics of planar maps, Diskret. Mat. 3 (1991) 24-27, in Russian.; · Zbl 0742.05034
[5] O.V. Borodin, Joint extension of two theorems of Kotzig on 3-polytopes, Combinatorica 13 (1993) 121-125. doi:; · Zbl 0777.05050 · doi:10.1007/BF01202794
[6] O.V. Borodin, The structure of neighborhoods of an edge in planar graphs and the simultaneous coloring of vertices, edges and faces, Mat. Zametki 53 (1993) 35-47, in Russian.;
[7] O.V. Borodin and D. Sanders, On light edges and triangles in planar graphs of minimum degree five, Math. Nachr. 170 (1994) 19-24. doi:; · Zbl 0813.05020 · doi:10.1002/mana.19941700103
[8] O.V. Borodin, Simultaneous coloring of edges and faces of plane graphs, Discrete Math. 128 (1994) 21-33. doi:; · Zbl 0807.05029 · doi:10.1016/0012-365X(94)90101-5
[9] O.V. Borodin, Structural theorem on plane graphs with application to the entire coloring, J. Graph Theory 23 (1996) 233-239. doi:; · Zbl 0863.05035 · doi:10.1002/(SICI)1097-0118(199611)23:3h233::AID-JGT3i3.0.CO;2-T
[10] O.V. Borodin, More about the weight of edges in planar graphs, Tatra Mt. Math. Publ. 9 (1996) 11-14.; · Zbl 0854.05039
[11] O.V. Borodin, A.V. Kostochka and D.R. Woodall, List edge and list total colourings of multigraphs, J. Combin. Theory Ser. B 71 (1997) 184-204. doi:; · Zbl 0876.05032 · doi:10.1006/jctb.1997.1780
[12] O.V. Borodin, A.O. Ivanova, A.V. Kostochka and N.N. Sheikh, Minimax degrees of quasiplanar graphs with no short cycles other than triangles, Taiwanese J. Math. 12 (2008) 873-886.; · Zbl 1163.05013
[13] O.V. Borodin, A.V. Kostochka, N.N. Sheikh and G. Yu, M-degrees of quadranglefree planar graphs, J. Graph Theory 60 (2009) 80-85. doi:; · Zbl 1161.05024 · doi:10.1002/jgt.20346
[14] O.V. Borodin, Colorings of plane graphs: A survey, Discrete Math. 313 (2013) 517-539. doi:; · Zbl 1259.05042 · doi:10.1016/j.disc.2012.11.011
[15] O.V. Borodin and A.O. Ivanova, Low edges in 3-polytopes, DiscreteMath. 338 (2015) 2234-2241. doi:; · Zbl 1321.52017 · doi:10.1016/j.disc.2015.05.018
[16] O.V. Borodin and A.O. Ivanova, The vertex-face weight of edges in 3-polytopes, Sibirsk. Mat. Zh. 56 (2015) 338-350, in Russian.; · Zbl 1331.52018
[17] R. Cole, L. Kowalik and R. Škrekovski, A generalization of Kotzig’s theorem and its application, SIAM J. Discrete Math. 21 (2007) 93-106. doi:; · Zbl 1138.05059 · doi:10.1137/050646196
[18] Z. Dvořák and R. Škrekovski, A theorem about contractible and light edge, SIAM J. Discrete Math. 20 (2006) 55-61. doi:; · Zbl 1110.05026 · doi:10.1137/05062189X
[19] B. Ferencová and T. Madaras, Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight, Discrete Math. 310 (2010) 1661-1675. doi:; · Zbl 1222.05217 · doi:10.1016/j.disc.2009.11.027
[20] Ph. Franklin, The four color problem, Amer. J. Math. 44 (1922) 225-236. doi:; · JFM 48.0664.02 · doi:10.2307/2370527
[21] B. Grünbaum, New views on some old questions of combinatorial geometry, in: Proc. Colloq. Int. sulle Theorie Combinatorie, Rome, 1973, Vol. 1 (Accad. Naz. dei Lincei, 1976) 451-468.;
[22] P. Hudák and T. Madaras, On doubly light triangles in plane graphs, Discrete Math. 313 (2013) 1978-1988. doi:; · Zbl 1277.05047 · doi:10.1016/j.disc.2012.11.018
[23] S. Jendrol’ and T. Madaras, On light subgraphs in plane graphs of minimum degree five, Discuss. Math. Graph Theory 16 (1996) 207-217. doi:; · Zbl 0877.05050 · doi:10.7151/dmgt.1035
[24] S. Jendrol’ and M. Maceková, Describing short paths in plane graphs of girth at least 5, Discrete Math. 338 (2015) 149-158. doi:; · Zbl 1302.05040 · doi:10.1016/j.disc.2014.09.014
[25] S. Jendrol’, M. Maceková and R. Soták, Note on 3-paths in plane graphs of girth 4, Discrete Math. 338 (2015) 1643-1648. doi:; · Zbl 1311.05042 · doi:10.1016/j.disc.2015.04.011
[26] S. Jendrol’ and H.-J. Voss, Light subgraphs of graphs embedded in the plane - A survey, Discrete Math. 313 (2013) 406-421. doi:; · Zbl 1259.05045 · doi:10.1016/j.disc.2012.11.007
[27] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. Čas. (Math. Slovaca) 5 (1955) 101-113, in Slovak.;
[28] A. Kotzig, From the theory of Eulerian polyhedrons, Mat.-Fyz. Čas. (Math. Slovaca) 13 (1963) 20-31, in Russian.; · Zbl 0134.19601
[29] H. Lebesgue, Quelques conséquences simples de la formule d’Euler , J. Math. Pures Appl. (9) 19 (1940) 27-43.; · JFM 66.0736.03
[30] T. Madaras and R. Škrekovski, Heavy paths, light stars, and big melons, Discrete Math. 286 (2004) 115-131. doi:; · Zbl 1053.05035 · doi:10.1016/j.disc.2003.11.052
[31] J. Nešetřil, A. Raspaud and E. Sopena, Colorings and girth of oriented planar graphs, Discrete Math. 165/166 (1997) 519-530. doi:; · Zbl 0873.05042 · doi:10.1016/S0012-365X(96)00198-7
[32] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426. doi:; · JFM 35.0511.01 · doi:10.1007/BF01444968
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.