TY - JOUR

T1 - Refined weight of edges in normal plane maps

AU - Batueva, Ts Ch D.

AU - Borodin, O. V.

AU - Bykov, M. A.

AU - Ivanova, A. O.

AU - Kazak, O. N.

AU - Nikiforov, D. V.

PY - 2017/11/1

Y1 - 2017/11/1

N2 - The weight w(e) of an edge e in a normal plane map (NPM) is the degree-sum of its end-vertices. An edge e=uv is of type (i,j) if d(u)≤i and d(v)≤j. In 1940, Lebesgue proved that every NPM has an edge of one of the types (3,11), (4,7), or (5,6), where 7 and 6 are best possible. In 1955, Kotzig proved that every 3-connected planar graph has an edge e with w(e)≤13, which bound is sharp. Borodin (1989), answering Erdős’ question, proved that every NPM has either a (3,10)-edge, or (4,7)-edge, or (5,6)-edge. A vertex is simplicial if it is completely surrounded by 3-faces. In 2010, Ferencová and Madaras conjectured (in different terms) that every 3-polytope without simplicial 3-vertices has an edge e with w(e)≤12. Recently, we confirmed this conjecture by proving that every NPM has either a simplicial 3-vertex adjacent to a vertex of degree at most 10, or an edge of types (3,9), (4,7), or (5,6). By a k(ℓ)-vertex we mean a k-vertex incident with precisely ℓ triangular faces. The purpose of our paper is to prove that every NPM has an edge of one of the following types: (3(3),10), (3(2),9), (3(1),7), (4(4),7), (4(3),6), (5(5),6), or (5,5), where all bounds are best possible. In particular, this implies that the bounds in (3,10), (4,7), and (5,6) can be attained only at NPMs having a simplicial 3-, 4-, or 5-vertex, respectively.

AB - The weight w(e) of an edge e in a normal plane map (NPM) is the degree-sum of its end-vertices. An edge e=uv is of type (i,j) if d(u)≤i and d(v)≤j. In 1940, Lebesgue proved that every NPM has an edge of one of the types (3,11), (4,7), or (5,6), where 7 and 6 are best possible. In 1955, Kotzig proved that every 3-connected planar graph has an edge e with w(e)≤13, which bound is sharp. Borodin (1989), answering Erdős’ question, proved that every NPM has either a (3,10)-edge, or (4,7)-edge, or (5,6)-edge. A vertex is simplicial if it is completely surrounded by 3-faces. In 2010, Ferencová and Madaras conjectured (in different terms) that every 3-polytope without simplicial 3-vertices has an edge e with w(e)≤12. Recently, we confirmed this conjecture by proving that every NPM has either a simplicial 3-vertex adjacent to a vertex of degree at most 10, or an edge of types (3,9), (4,7), or (5,6). By a k(ℓ)-vertex we mean a k-vertex incident with precisely ℓ triangular faces. The purpose of our paper is to prove that every NPM has an edge of one of the following types: (3(3),10), (3(2),9), (3(1),7), (4(4),7), (4(3),6), (5(5),6), or (5,5), where all bounds are best possible. In particular, this implies that the bounds in (3,10), (4,7), and (5,6) can be attained only at NPMs having a simplicial 3-, 4-, or 5-vertex, respectively.

KW - 3-polytope

KW - Planar graph

KW - Plane map

KW - Structure properties

KW - Weight

KW - COLORINGS

KW - GRAPHS

UR - http://www.scopus.com/inward/record.url?scp=85006757703&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2016.10.007

DO - 10.1016/j.disc.2016.10.007

M3 - Article

AN - SCOPUS:85006757703

VL - 340

SP - 2659

EP - 2664

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 11

ER -