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