A conjecture of Borodin and a coloring of Grunbaum

被引：3

作者：

Rautenbach, Dieter ^{[1
]}

机构：

[1] Tech Univ Ilmenau, Inst Math, D-98684 Ilmenau, Germany

来源：

JOURNAL OF GRAPH THEORY | 2008年 / 58卷 / 02期

关键词：

coloring; acyclic coloring; degenerate; planar graph;

D O I：

10.1002/jgt.20299

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In 1976, Borodin conjectured that every planar graph has a 5-coloring such that the union of every k color classes with 1 <= k <= 4 induces a (k-1)-degenerate graph. We prove the existence of such a coloring using 18 colors. (C) 2008 Wiley Periodicals, Inc.

引用

页码：139 / 147

页数：9

共 14 条

[1] EVERY PLANAR GRAPH HAS AN ACYCLIC-7-COLORING [J].

ALBERTSON, MO ;

BERMAN, DM .

ISRAEL JOURNAL OF MATHEMATICS, 1977, 28 (1-2) :169-174

[2]

Albertson MO, 2004, ELECTRON J COMB, V11

[3] ACYCLIC COLORING OF GRAPHS [J].

ALON, N ;

MCDIARMID, C ;

REED, B .

RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (03) :277-288

[4]

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

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

BORODIN, OV .

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

[6] Acyclic list 7-coloring of planar graphs [J].

Borodin, OV ;

Flaass, DGF ;

Kostochka, AV ;

Raspaud, A ;

Sopena, E .

JOURNAL OF GRAPH THEORY, 2002, 40 (02) :83-90

[7] Star coloring of graphs [J].

Fertin, G ;

Raspaud, A ;

Reed, B .

JOURNAL OF GRAPH THEORY, 2004, 47 (03) :163-182

[8]

Gonçalves D, 2005, LECT NOTES COMPUT SC, V3787, P239

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

GRUNBAUM, B .

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

[10]

Jensen T. R., 1995, Graph Coloring Problems

← 1 2 →