A note on the Three Color Problem on planar graphs without 4-and 5-cycles and without ext-triangular 7-cycles

被引：0

作者：

Liang, Zuosong ^{[1
]}

Xu, Guangjun ^{[2
]}

Bai, Chunsong ^{[3
]}

机构：

[1] Guangxi Minzu Univ, Ctr Appl Math Guangxi, Sch Math & Phys, Nanning 530006, Peoples R China

[2] Zunyi Normal Univ, Sch Math, Zunyi 563000, Guizhou, Peoples R China

[3] Huainan Normal Univ, Sch Finance & Math, Huainan 232038, Peoples R China

来源：

DISCRETE MATHEMATICS | 2023年 / 346卷 / 01期

关键词：

Coloring; 3-colorable; Planar graph;

D O I：

10.1016/j.disc.2022.113192

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Steinberg conjectured in 1976 that every planar graph with no cycles of length four or five is 3-colorable. This conjecture is disproved by constructing a planar graph with no cycles of length four or five but intersecting triangles. Jin et al. proved that plane graphs without 4-and 5-cycles and without ext-triangular 7-cycles are 3-colorable [SIAM J. Discrete Math. 31 (3) (2017) 1836-1847]. In this paper, we point out a mistake of their proof and give an improved proof.(c) 2022 Elsevier B.V. All rights reserved.

引用

页数：3

共 8 条

[1]

ABBOTT HL, 1991, ARS COMBINATORIA, V32, P203

[2] Planar graphs without 5-and 7-cycles and without adjacent triangles are 3-colorable [J].

Borodin, O. V. ;

Glebov, A. N. ;

Montassier, M. ;

Raspaud, A. .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2009, 99 (04) :668-673

[3]

Borodin OV, 1996, J GRAPH THEOR, V21, P183

[4] Planar graphs without cycles of length from 4 to 7 are 3-colorable [J].

Borodin, OV ;

Glebov, AN ;

Raspaud, A ;

Salavatipour, MR .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 93 (02) :303-311

[5] Steinberg's Conjecture is false [J].

Cohen-Addad, Vincent ;

Hebdige, Michael ;

Kral, Daniel ;

Li, Zhentao ;

Salgado, Esteban .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 122 :452-456

[6] PLANE GRAPHS WITHOUT 4-AND 5-CYCLES AND WITHOUT EXT-TRIANGULAR 7-CYCLES ARE 3-COLORABLE [J].

Jin, Ligang ;

Kang, Yingli ;

Schubert, Michael ;

Wang, Yingqian .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (03) :1836-1847

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

SANDERS, DP ;

ZHAO, Y .

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

[8] 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 →