Every 3-polytope with minimum degree 5 has a 6-cycle with maximum degree at most 11

被引：6

作者：

Borodin, O. V. ^{[1
,2
]}

Ivanova, A. O. ^{[3
]}

Kostochka, A. V. ^{[1
,4
]}

机构：

[1] Sobolev Inst Math, Novosibirsk 630090, Russia

[2] Novosibirsk State Univ, Novosibirsk 630090, Russia

[3] Ammosov North Eastern Fed Univ, Yakutsk 677891, Russia

[4] Univ Illinois, Urbana, IL 61801 USA

来源：

DISCRETE MATHEMATICS | 2014年 / 315卷

基金：

美国国家科学基金会; 俄罗斯基础研究基金会;

关键词：

Planar graph; Plane map; Structure properties; 3-polytope; Weight; LIGHT SUBGRAPHS; PLANE GRAPHS; CYCLES;

D O I：

10.1016/j.disc.2013.10.021

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let phi(P)(C-6) (respectively, phi(T)(C-6)) be the minimum integer k with the property that every 3-polytope (respectively, every plane triangulation) with minimum degree 5 has a 6-cycle with all vertices of degree at most k. In 1999, S. Jendrol' and T. Madaras proved that 10 <= phi(T)(C-6) <= 11. It is also known, due to B. Mohar, R. Skrekovski and H.-J. Voss (2003), that phi(P)(C-6) <= 107. We prove that phi(P)(C-6) = phi(T)(C-6) = 11. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：128 / 134

页数：7

共 22 条

[1]

BORODIN O, 1992, MATH NACHR, V158, P109

[2] Colorings of plane graphs: A survey [J].

Borodin, O. V. .

DISCRETE MATHEMATICS, 2013, 313 (04) :517-539

[3]

Borodin O.V., 1998, DISCUSS MATH GRAPH T, V18, P159, DOI DOI 10.7151/DMGT.1071

[4] SOLUTION OF PROBLEMS OF KOTZIG AND GRUNBAUM CONCERNING THE ISOLATION OF CYCLES IN PLANAR GRAPHS [J].

BORODIN, OV .

MATHEMATICAL NOTES, 1989, 46 (5-6) :835-837

[5]

Borodin OV, 1996, J GRAPH THEOR, V23, P233, DOI 10.1002/(SICI)1097-0118(199611)23:3<233::AID-JGT3>3.0.CO

[6]

2-T

[7] ACYCLIC COLORINGS OF PLANAR GRAPHS [J].

BORODIN, OV .

DISCRETE MATHEMATICS, 1979, 25 (03) :211-236

[8] Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight [J].

Ferencova, Barbora ;

Madaras, Tomas .

DISCRETE MATHEMATICS, 2010, 310 (12) :1661-1675

[9] The four color problem [J].

Franklin, P .

AMERICAN JOURNAL OF MATHEMATICS, 1922, 44 :225-236

[10]

Grunbaum B., 1975, MATH ASS AM STUDIES, V12, P201

← 1 2 3 →