A NOTE ON 3-COLORABLE PLANE GRAPHS WITHOUT 5- AND 7-CYCLES

被引：6

作者：

Xu, Baogang ^{[1
]}

机构：

[1] Nanjing Normal Univ, Sch Math & Comp Sci, 122 Ninghai Rd, Nanjing 210097, Peoples R China

来源：

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS | 2009年 / 1卷 / 03期

关键词：

Plane graph; cycle; coloring;

D O I：

10.1142/S1793830909000270

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In [1], Borodin et al. figured out a gap of [5], and gave a new proof with the similar technique. The purpose of this note is to fix the gap of [5] by slightly revising the definition of special faces, and adding a few lines of explanation in the original proofs of [5] (new added text are all in italic type).

引用

页码：347 / 353

页数：7

共 6 条

[1] 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

[2] 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

[3] A sufficient condition for planar graphs to be 3-colorable [J].

Borodin, OV ;

Raspaud, A .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 88 (01) :17-27

[4]

Steinberg R., 1993, GRAPH THEORY, V55, P211, DOI DOI 10.1016/S0167-5060(08)70391-1

[5] A 3-color theorem on plane graphs without 5-circuits [J].

Xu, Bao Gang .

ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2007, 23 (06) :1059-1062

[6] On 3-colorable plane graphs without 5-and 7-cycles [J].

Xu, Baogang .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (06) :958-963

← 1 →