A sufficient condition for a planar graph to be 3-choosable

被引：15
作者：
Shen, Liang [1 ]
Wang, Yingqian [1 ]
机构：
[1] Zhejiang Normal Univ, Coll Math Phys & Informat Engn, Jinhua 321004, Peoples R China
来源：
INFORMATION PROCESSING LETTERS | 2007年 / 104卷 / 04期
基金：
中国国家自然科学基金;
关键词：
combinatorial problems; planar graph; cycle; choosability;
D O I：
10.1016/j.ipl.2007.06.005
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
It is shown that a planar graph without cycles of length 4, 6, 8, or 9 is 3-choosable. (c) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：146 / 151
页数：6
相关论文
共 9 条
[1]   COLORINGS AND ORIENTATIONS OF GRAPHS [J].
ALON, N ;
TARSI, M .
COMBINATORICA, 1992, 12 (02) :125-134
[2]   The 3-choosability of plane graphs of girth 4 [J].
Lam, PCB ;
Shiu, WC ;
Song, ZM .
DISCRETE MATHEMATICS, 2005, 294 (03) :297-301
[3]   A note on the not 3-choosability of some families of planar graphs [J].
Montassier, M .
INFORMATION PROCESSING LETTERS, 2006, 99 (02) :68-71
[4]   Bordeaux 3-color conjecture and 3-choosability [J].
Montassier, M ;
Raspaud, A ;
Wang, WF .
DISCRETE MATHEMATICS, 2006, 306 (06) :573-579
[5]   EVERY PLANAR GRAPH IS 5-CHOOSABLE [J].
THOMASSEN, C .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 62 (01) :180-181
[6]   3-LIST-COLORING PLANAR GRAPHS OF GIRTH-5 [J].
THOMASSEN, C .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 64 (01) :101-107
[7]   LIST COLORINGS OF PLANAR GRAPHS [J].
VOIGT, M .
DISCRETE MATHEMATICS, 1993, 120 (1-3) :215-219
[8]   A note on 3-choosability of planar graphs without certain cycles [J].
Zhang, L ;
Wu, BD .
DISCRETE MATHEMATICS, 2005, 297 (1-3) :206-209
[9]   Analysis of fragment size and ejection velocity at high strain rate [J].
Zhang, YQ ;
Lu, Y ;
Hao, H .
INTERNATIONAL JOURNAL OF MECHANICAL SCIENCES, 2004, 46 (01) :27-34
1