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 [J].

ALON, N ;

MCDIARMID, C ;

REED, B .

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 [J].

Esperet, Louis ;

Parreau, Aline .

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 [J].

GRUNBAUM, B .

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

[10] New approach to nonrepetitive sequences [J].

Grytczuk, Jaroslaw ;

Kozik, Jakub ;

Micek, Piotr .

RANDOM STRUCTURES & ALGORITHMS, 2013, 42 (02) :214-225

← 1 2 3 →