PLANE GRAPHS WITHOUT 4-AND 5-CYCLES AND WITHOUT EXT-TRIANGULAR 7-CYCLES ARE 3-COLORABLE

被引：4

作者：

Jin, Ligang ^{[1
]}

Kang, Yingli ^{[2
,3
]}

Schubert, Michael ^{[2
,3
]}

Wang, Yingqian ^{[1
]}

机构：

[1] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Peoples R China

[2] Paderborn Univ, Inst Math, D-33102 Paderborn, Germany

[3] Paderborn Univ, Paderborn Ctr Adv Studies, D-33102 Paderborn, Germany

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2017年 / 31卷 / 03期

基金：

中国国家自然科学基金;

关键词：

plane graphs; 3-colorability; Steinberg's conjecture; discharging; CYCLES;

D O I：

10.1137/16M1086418

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Steinberg's conjecture states that planar graphs without 4- and 5-cycles are 3-colorable. This conjecture, though disproved recently, has motivated a lot of work in the literature. A plane graph is a planar graph G together with an embedding of G into the Euclidean plane. A 7-cycle C of a plane graph is ext-triangular if it is adjacent to a triangle T such that the areas inside C and inside T have no intersection. In this paper, we prove that plane graphs without 4 and 5-cycles are 3-colorable if they contain no ext-triangular 7-cycles, which improves a number of known results. In particular, our result implies that (1) planar graphs without 4-, 5-, and 7-cycles are 3-colorable, and (2) planar graphs without 4-, 5-, and 8-cycles are 3-colorable.

引用

页码：1836 / 1847

页数：12

共 17 条

[11] On the 3-colorability of planar graphs without 4-, 7-and 9-cycles [J].

Lu, Huajing ;

Wang, Yingqian ;

Wang, Weifan ;

Bu, Yuehua ;

Montassier, Mickael ;

Raspaud, Andre .

DISCRETE MATHEMATICS, 2009, 309 (13) :4596-4607

[12]

MONDAL S. A., 2011, DISCUSS MATH GRAPH T, V31, P775

[13] A NOTE ON THE 3-COLOR PROBLEM [J].

SANDERS, DP ;

ZHAO, Y .

GRAPHS AND COMBINATORICS, 1995, 11 (01) :91-94

[14]

Steinberg R., 1993, Quo Vadis. Gr. Theory Ann. Discrete Math., V55, P211, DOI DOI 10.1016/S0167-5060(08)70391-1

[15] Planar graphs without 4,6,8-cycles are 3-colorable [J].

Wang, Wei-fan ;

Chen, Min .

SCIENCE IN CHINA SERIES A-MATHEMATICS, 2007, 50 (11) :1552-1562

[16]

[王应前 Wang Yingqian], 2013, [中国科学. 数学, Scientia Sinica Mathematica], V43, P1145

[17] A NOTE ON 3-COLORABLE PLANE GRAPHS WITHOUT 5- AND 7-CYCLES [J].

Xu, Baogang .

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2009, 1 (03) :347-353

← 1 2 →