Choosability of Toroidal Graphs Without Short Cycles

被引：9

作者：

Cai, Leizhen ^{[1
]}

Wang, Weifan ^{[2
]}

Zhu, Xuding ^{[3
]}

机构：

[1] Chinese Univ Hong Kong, Dept Comp Sci & Engn, Shatin, Hong Kong, Peoples R China

[2] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Peoples R China

[3] Natl Sun Yat Sen Univ, Dept Appl Math, Kaohsiung 804, Taiwan

来源：

JOURNAL OF GRAPH THEORY | 2010年 / 65卷 / 01期

关键词：

choosability; list coloring; toroidal graph; cycle; discharging method; PLANAR GRAPHS; EDGE CHOOSABILITY; THEOREM; TORUS; COLORINGS; SURFACES;

D O I：

10.1002/jgt.20460

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a toroidal graph without cycles of a fixed length k, and xi(G) the list chromatic number of G. We establish tight upper bounds of chi(G) for the following values of k: chi(G)<={4 if k is an element of {3,4,5} 5 if k=6 6 if k=7 (C) 2009 Wiley Periodicals, Inc. J Graph Theory 65: 1-15, 2010

引用

页码：1 / 15

页数：15

共 29 条

[11] Grotzsch H., 1959, MATH NAT REIHE, V8, P109
[12] 3-COLORING GRAPHS EMBEDDED ON SURFACES WITH ALL FACES EVEN-SIDED
HUTCHINSON, JP
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 65 (01) : 139 - 155
[13] Jensen T., 1995, Graph Coloring Problems, P115
[14] LIST EDGE CHROMATIC NUMBER OF GRAPHS WITH LARGE GIRTH
KOSTOCHKA, AV
[J]. DISCRETE MATHEMATICS, 1992, 101 (1-3) : 189 - 201
[15] Coloring even-faced graphs in the torus and the Klein bottle
Kral, Daniel
Thomas, Robin
[J]. COMBINATORICA, 2008, 28 (03) : 325 - 341
[16] 4-COLOR THEOREM FOR TOROIDAL GRAPHS
KRONK, HV
WHITE, AT
[J]. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1972, 34 (01) : 83 - &
[17] Lam PCB, 1999, J COMB THEORY B, V76, P117
[18] On structure of some plane graphs with application to choosability
Lam, PCB
Shiu, WC
Xu, BG
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 82 (02) : 285 - 296
[19] 5-COLORING GRAPHS ON THE TORUS
THOMASSEN, C
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 62 (01) : 11 - 33
[20] EVERY PLANAR GRAPH IS 5-CHOOSABLE
THOMASSEN, C
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 62 (01) : 180 - 181

← 1 2 3 →