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 条

[1] SOME COUNTEREXAMPLES ASSOCIATED WITH THE 3-COLOR PROBLEM
AKSIONOV, VA
MELNIKOV, LS
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1980, 28 (01) : 1 - 9
[2] COLORINGS AND ORIENTATIONS OF GRAPHS
ALON, N
TARSI, M
[J]. COMBINATORICA, 1992, 12 (02) : 125 - 134
[3] [Anonymous], 1890, Quart. J. Math.
[4] Chromatic numbers of quadrangulations on closed surfaces
Archdeacon, D
Hutchinson, J
Nakamoto, A
Negam, S
Ota, K
[J]. JOURNAL OF GRAPH THEORY, 2001, 37 (02) : 100 - 114
[5] Böhme T, 1999, J GRAPH THEOR, V32, P327, DOI 10.1002/(SICI)1097-0118(199912)32:4<327::AID-JGT2>3.0.CO
[6] 2-B
[7] MAP-COLOUR THEOREMS
DIRAC, GA
[J]. CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1952, 4 (04): : 480 - 490
[8] ERDOS R, 1980, C NUMER, V26, P125
[9] PLANAR GRAPHS WITHOUT 7-CYCLES ARE 4-CHOOSABLE
Farzad, Babak
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (03) : 1179 - 1199
[10] Planar graphs without cycles of specific lengths
Fijavz, G
Juvan, M
Mohar, B
Skrekovski, R
[J]. EUROPEAN JOURNAL OF COMBINATORICS, 2002, 23 (04) : 377 - 388

← 1 2 3 →