A note on acyclic vertex-colorings

被引：7

作者：

Sereni, Jean-Sebastien ^{[1
]}

Volec, Jan ^{[2
,3
,4
]}

机构：

[1] CNRS, LORIA, Vandoeuvre Les Nancy, France

[2] ETH, Dept Math, CH-8092 Zurich, Switzerland

[3] Univ Warwick, Inst Math, Coventry CV4 7AL, W Midlands, England

[4] Univ Warwick, DIMAP, Coventry CV4 7AL, W Midlands, England

来源：

JOURNAL OF COMBINATORICS | 2016年 / 7卷 / 04期

关键词：

Acyclic coloring; entropy compression; local lemma;

D O I：

10.4310/JOC.2016.v7.n4.a8

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We prove that the acyclic chromatic number of a graph with maximum degree Delta is less than 2.835 Delta(4/3) + Delta. This improves the previous upper bound, which was 50 Delta(4/3). To do so, we draw inspiration from works by Alon, McDiarmid & Reed and by Esperet & Parreau.

引用

页码：725 / 737

页数：13

共 21 条

[1] ALBERTSON MO, 1976, C NUMERANTIUM, V17, P51
[2] ACYCLIC COLORING OF GRAPHS
ALON, N
MCDIARMID, C
REED, B
[J]. RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (03) : 277 - 288
[3] Drmota M., 2004, CUBO, V6, P105
[4] Dujmovic V., COMBINATORI IN PRESS
[5] Erd P., 1975, C MATH SOC J ANOS BO, V10, P609
[6] Acyclic edge-coloring using entropy compression
Esperet, Louis
Parreau, Aline
[J]. EUROPEAN JOURNAL OF COMBINATORICS, 2013, 34 (06) : 1019 - 1027
[7] Fortnow L., 2009, KOLMOGOROV COMPLEXIT
[8] Goncalves D., 2015, 14064380 ARXIV
[9] ACYCLIC COLORINGS OF PLANAR GRAPHS
GRUNBAUM, B
[J]. ISRAEL JOURNAL OF MATHEMATICS, 1973, 14 (04) : 390 - 408
[10] New approach to nonrepetitive sequences
Grytczuk, Jaroslaw
Kozik, Jakub
Micek, Piotr
[J]. RANDOM STRUCTURES & ALGORITHMS, 2013, 42 (02) : 214 - 225

← 1 2 3 →