On the 3-colorability of planar graphs without 4-, 7-and 9-cycles

被引：7

作者：

Lu, Huajing ^{[1
]}

Wang, Yingqian ^{[1
]}

Wang, Weifan ^{[1
]}

Bu, Yuehua ^{[1
]}

Montassier, Mickael ^{[2
]}

Raspaud, Andre ^{[2
]}

机构：

[1] Zhejiang Normal Univ, Coll Math Phys & Informat Engn, Jinhua 321004, Peoples R China

[2] Univ Bordeaux, LaBRI, F-33405 Talence, France

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 13期

关键词：

Planar graphs; Cycles; Extendability; Coloring; CYCLES;

D O I：

10.1016/j.disc.2009.02.030

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

引用

页码：4596 / 4607

页数：12

共 17 条

[1]

ABBOTT HL, 1991, ARS COMBINATORIA, V32, P203

[2]

Bondy J.A., 2008, GTM

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

[4]

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

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

[6] Three-coloring planar graphs without short cycles [J].

Chen, Min ;

Raspaud, Andre ;

Wang, Weifan .

INFORMATION PROCESSING LETTERS, 2007, 101 (03) :134-138

[7]

Jensen T., 1995, Graph Coloring Problems, P115

[8] On 3-colorable planar graphs without cycles of four lengths [J].

Luo, Xiaofang ;

Chen, Min ;

Wang, Weifan .

INFORMATION PROCESSING LETTERS, 2007, 103 (04) :150-156

[9]

SANDERS DP, 1995, GRAPHS COMBIN, V11, P92

[10] A sufficient condition for a planar graph to be 3-choosable [J].

Shen, Liang ;

Wang, Yingqian .

INFORMATION PROCESSING LETTERS, 2007, 104 (04) :146-151

← 1 2 →