THE TWO-COLORING NUMBER AND DEGENERATE COLORINGS OF PLANAR GRAPHS

被引：10

作者：

Kierstead, Hal ^{[1
]}

Mohar, Bojan ^{[2
]}

Spacapan, Simon ^{[3
]}

Yang, Daqing ^{[4
]}

Zhu, Xuding ^{[5
,6
]}

机构：

[1] Arizona State Univ, Dept Math & Stat, Tempe, AZ 85287 USA

[2] Simon Fraser Univ, Dept Math, Burnaby, BC V5A 1S6, Canada

[3] Univ Maribor, FME, SLO-2000 Maribor, Slovenia

[4] Fuzhou Univ, Ctr Discrete Math, Fuzhou 350002, Fujian, Peoples R China

[5] Natl Sun Yat Sen Univ, Dept Appl Math, Kaohsiung 80424, Taiwan

[6] Natl Taiwan Univ, Natl Ctr Theoret Sci, Taipei 10617, Taiwan

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2009年 / 23卷 / 03期

基金：

加拿大自然科学与工程研究理事会;

关键词：

two-coloring number; degenerate coloring; planar graph; GAME; TRIANGULATIONS;

D O I：

10.1137/070703697

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The two-coloring number of graphs, which was originally introduced in the study of the game chromatic number, also gives an upper bound on the degenerate chromatic number as introduced by Borodin. It is proved that the two-coloring number of any planar graph is at most nine. As a consequence, the degenerate list chromatic number of any planar graph is at most nine. It is also shown that the degenerate diagonal chromatic number is at most 11 and the degenerate diagonal list chromatic number is at most 12 for all planar graphs.

引用

页码：1548 / 1560

页数：13

共 16 条

[1]

Borodin O.V., 1976, SOV MATH DOKL, P1499

[2]

Borodin O.V., 1976, METODY DISKRET ANALI, V28, P3

[3] DIAGONAL 11-COLORING OF PLANE TRIANGULATIONS [J].

BORODIN, OV .

JOURNAL OF GRAPH THEORY, 1990, 14 (06) :701-704

[4]

BOUCHET A, 1987, ARS COMBINATORIA, V24, P67

[5] GRAPHS WITH LINEARLY BOUNDED RAMSEY NUMBERS [J].

CHEN, GT ;

SCHELP, RH .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1993, 57 (01) :138-149

[6] ACYCLIC COLORINGS OF PLANAR GRAPHS [J].

GRUNBAUM, B .

ISRAEL JOURNAL OF MATHEMATICS, 1973, 14 (04) :390-408

[7]

Jensen T., 1995, Graph Coloring Problems, P115

[8] Orderings on graphs and game coloring number [J].

Kierstead, HA ;

Yang, DQ .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2003, 20 (03) :255-264

[9] PLANAR GRAPH-COLORING WITH AN UNCOOPERATIVE PARTNER [J].

KIERSTEAD, HA ;

TROTTER, WT .

JOURNAL OF GRAPH THEORY, 1994, 18 (06) :569-584

[10]

RAUTENBACH D, 2006, ELECT NOTES DISCRETE, V24, P187

← 1 2 →