STAR COLORING AND ACYCLIC COLORING OF LOCALLY PLANAR GRAPHS

被引：10

作者：

Kawarabayashi, Ken-ichi ^{[1
]}

Mohar, Bojan ^{[2
]}

机构：

[1] Tohoku Univ, Grad Sch Informat Sci, Sendai, Miyagi 9808579, Japan

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

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2010年 / 24卷 / 01期

基金：

加拿大自然科学与工程研究理事会; 日本学术振兴会;

关键词：

acyclic coloring; star coloring; genus; edge-width; locally planar graph;

D O I：

10.1137/060674211

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

It is proved that every graph embedded in a fixed surface with sufficiently large edge-width is acyclically 7-colorable and that its star chromatic number is at most 2s(0)* + 3, where s(0)* <= 20 is the maximum star chromatic number for the class of all planar graphs.

引用

页码：56 / 71

页数：16

共 11 条

[1]

Albertson MO, 2004, ELECTRON J COMB, V11

[2] On acyclic colorings of graphs on surfaces [J].

Alon, N ;

Mohar, B ;

Sanders, DP .

ISRAEL JOURNAL OF MATHEMATICS, 1996, 94 :273-283

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

BORODIN, OV .

DISCRETE MATHEMATICS, 1979, 25 (03) :211-236

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

GRUNBAUM, B .

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

[5]

Jensen T., 1995, Graph Coloring Problems, P115

[6]

KAWARABAYASHI K, PLANE HIGHER SURFACE

[7] Acyclic colorings of locally planar graphs [J].

Mohar, B .

EUROPEAN JOURNAL OF COMBINATORICS, 2005, 26 (3-4) :491-503

[8]

Mohar B., 2001, JH STUD MATH SCI, DOI 10.56021/9780801866890

[9] GRAPH MINORS .7. DISJOINT PATHS ON A SURFACE [J].

ROBERTSON, N ;

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1988, 45 (02) :212-254

[10] 5-COLORING MAPS ON SURFACES [J].

THOMASSEN, C .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1993, 59 (01) :89-105

← 1 2 →