Geodesic
An Extension of Kotzig’s Theorem
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 889-897.

Voir la notice de l'article provenant de la source Library of Science

In 1955, Kotzig 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) ≤ i and d(v) ≤ j. Borodin (1991) proved that every normal plane map contains an edge of one of the types (3, 10), (4, 7), or (5, 6), which is tight. Cole, Kowalik, and Škrekovski (2007) deduced from this result by Borodin that Kotzig’s bound of 13 is valid for all planar graphs with minimum degree δ at least 2 in which every d-vertex, d ≥ 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 ≥ 1 that every plane graph with δ ≥ 2 and no d-vertex, d ≥ 11+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.
Keywords: plane graph, normal plane map, structural property, weight 
@article{DMGT_2016_36_4_a9,
     author = {Aksenov, Valerii A. and Borodin, Oleg V. and Ivanova, Anna O.},
     title = {An {Extension} of {Kotzig{\textquoteright}s} {Theorem}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {889--897},
     publisher = {mathdoc},
     volume = {36},
     number = {4},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a9/}
}
TY  - JOUR
AU  - Aksenov, Valerii A.
AU  - Borodin, Oleg V.
AU  - Ivanova, Anna O.
TI  - An Extension of Kotzig’s Theorem
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 889
EP  - 897
VL  - 36
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a9/
LA  - en
ID  - DMGT_2016_36_4_a9
ER  - 
%0 Journal Article
%A Aksenov, Valerii A.
%A Borodin, Oleg V.
%A Ivanova, Anna O.
%T An Extension of Kotzig’s Theorem
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 889-897
%V 36
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a9/
%G en
%F DMGT_2016_36_4_a9
Aksenov, Valerii A.; Borodin, Oleg V.; Ivanova, Anna O. An Extension of Kotzig’s Theorem. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 889-897. http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a9/

[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: 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.

[3] O.V. Borodin, On the total coloring of planar graphs, J. Reine Angew. Math. 394 (1989) 180-185.

[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.

[5] O.V. Borodin, Joint extension of two theorems of Kotzig on 3-polytopes, Combinatorica 13 (1993) 121-125. 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: 10.1002/mana.19941700103

[8] O.V. Borodin, Simultaneous coloring of edges and faces of plane graphs, Discrete Math. 128 (1994) 21-33. 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: 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.

[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: 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.

[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: 10.1002/jgt.20346

[14] O.V. Borodin, Colorings of plane graphs: A survey, Discrete Math. 313 (2013) 517-539. 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: 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.

[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: 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: 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: 10.1016/j.disc.2009.11.027

[20] Ph. Franklin, The four color problem, Amer. J. Math. 44 (1922) 225-236. 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: 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: 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: 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: 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: 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.

[29] H. Lebesgue, Quelques conséquences simples de la formule d’Euler, J. Math. Pures Appl. (9) 19 (1940) 27-43.

[30] T. Madaras and R. Škrekovski, Heavy paths, light stars, and big melons, Discrete Math. 286 (2004) 115-131. 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: 10.1016/S0012-365X(96)00198-7

[32] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426. doi: 10.1007/BF01444968