# An Extension of Kotzig’s Theorem

Valerii A. Aksenov; Oleg V. Borodin; Anna O. Ivanova

Discussiones Mathematicae Graph Theory (2016)

- Volume: 36, Issue: 4, page 889-897
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topValerii A. Aksenov, Oleg V. Borodin, and Anna O. Ivanova. "An Extension of Kotzig’s Theorem." Discussiones Mathematicae Graph Theory 36.4 (2016): 889-897. <http://eudml.org/doc/287057>.

@article{ValeriiA2016,

abstract = {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.},

author = {Valerii A. Aksenov, Oleg V. Borodin, Anna O. Ivanova},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {plane graph; normal plane map; structural property; weight},

language = {eng},

number = {4},

pages = {889-897},

title = {An Extension of Kotzig’s Theorem},

url = {http://eudml.org/doc/287057},

volume = {36},

year = {2016},

}

TY - JOUR

AU - Valerii A. Aksenov

AU - Oleg V. Borodin

AU - Anna O. Ivanova

TI - An Extension of Kotzig’s Theorem

JO - Discussiones Mathematicae Graph Theory

PY - 2016

VL - 36

IS - 4

SP - 889

EP - 897

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

LA - eng

KW - plane graph; normal plane map; structural property; weight

UR - http://eudml.org/doc/287057

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.