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/