A note on 3-choosability of planar graphs without certain cycles

被引：20

作者：

Zhang, L ^{[1
]}

Wu, BD

机构：

[1] Chinese Acad Sci, Acad Math & Syst Sci, Inst Syst Sci, Beijing 100080, Peoples R China

[2] Xinjiang Univ Urumqi, Coll Math & Syst Sci, Xinjiang 830046, Peoples R China

来源：

DISCRETE MATHEMATICS | 2005年 / 297卷 / 1-3期

关键词：

planar graph; cycle; choosability;

D O I：

10.1016/j.disc.2005.05.001

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Steinberg asked whether every planar graph without 4 and 5 cycles is 3-colorable. Borodin, and independently Sanders and Zhao, showed that every planar graph without any cycle of length between 4 and 9 is 3-colorable. We improve this result by showing that every planar graph without any cycle of length 4, 5, 6, or 9 is 3-choosable. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：206 / 209

页数：4

共 10 条

[1]

ABBOTT HL, 1991, ARS COMBINATORIA, V32, P203

[2] COLORINGS AND ORIENTATIONS OF GRAPHS [J].

ALON, N ;

TARSI, M .

COMBINATORICA, 1992, 12 (02) :125-134

[3]

Borodin OV, 1996, ARS COMBINATORIA, V43, P191

[4]

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

[5]

BORODIN OV, UNPUB PLANAR GRAPHS

[6]

Grotzsch H., 1959, MATH NAT REIHE, V8, P109

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

SANDERS, DP ;

ZHAO, Y .

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

[8]

Steinberg R., 1993, ANN DISCR M, V55, P211, DOI DOI 10.1016/S0167-5060(08)70391-1

[9] 3-LIST-COLORING PLANAR GRAPHS OF GIRTH-5 [J].

THOMASSEN, C .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 64 (01) :101-107

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