Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable

被引：8
作者：
Wang, Yingqian [1 ]
Lu, Huajing [1 ]
Chen, Ming [2 ]
机构：
[1] Zhejiang Normal Univ, Coll Math Phys & Informat Engn, Jinhua 321004, Peoples R China
[2] Jiaxing Univ, Coll Math & Informat Engn, Jiaxing 314001, Peoples R China
来源：
DISCRETE MATHEMATICS | 2010年 / 310卷 / 01期
关键词：
Planar graph; Cycle; Choosability; Colorability; COLORINGS;
D O I：
10.1016/j.disc.2009.08.005
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
It is shown that a planar graph without cycles of length 4, 5, 8, or 9 is 3-choosable. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码：147 / 158
页数：12
相关论文
共 18 条
[1]   COLORINGS AND ORIENTATIONS OF GRAPHS [J].
ALON, N ;
TARSI, M .
COMBINATORICA, 1992, 12 (02) :125-134
[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]  
Erdos P., 1979, P W COAST C COMB GRA, P125
[4]   The complexity of planar graph choosability [J].
Gutner, S .
DISCRETE MATHEMATICS, 1996, 159 (1-3) :119-130
[5]   The 3-choosability of plane graphs of girth 4 [J].
Lam, PCB ;
Shiu, WC ;
Song, ZM .
DISCRETE MATHEMATICS, 2005, 294 (03) :297-301
[6]   A note on the not 3-choosability of some families of planar graphs [J].
Montassier, M .
INFORMATION PROCESSING LETTERS, 2006, 99 (02) :68-71
[7]   Bordeaux 3-color conjecture and 3-choosability [J].
Montassier, M ;
Raspaud, A ;
Wang, WF .
DISCRETE MATHEMATICS, 2006, 306 (06) :573-579
[8]   A sufficient condition for a planar graph to be 3-choosable [J].
Shen, Liang ;
Wang, Yingqian .
INFORMATION PROCESSING LETTERS, 2007, 104 (04) :146-151
[9]   EVERY PLANAR GRAPH IS 5-CHOOSABLE [J].
THOMASSEN, C .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 62 (01) :180-181
[10]   3-LIST-COLORING PLANAR GRAPHS OF GIRTH-5 [J].
THOMASSEN, C .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 64 (01) :101-107
12