Acyclic coloring of graphs and entropy compression method

被引：6

作者：

Goncalves, Daniel ^{[1
]}

Montassier, Mickael ^{[1
]}

Pinlou, Alexandre ^{[1
]}

机构：

[1] Univ Montpellier, CNRS, LIRMM, Montpellier, France

来源：

DISCRETE MATHEMATICS | 2020年 / 343卷 / 04期

关键词：

Graph; Acyclic coloring; Maximum degree; MAXIMUM DEGREE; BOUNDS;

D O I：

10.1016/j.disc.2019.111772

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Based on the algorithmic proof of Lovasz local lemma due to Moser and Tardos, Dujmovic et al. (2016) initiated the use of the so-called entropy compression method for graph coloring problems. Then, using the same approach Esperet and Parreau (2013) proved new upper bounds for several chromatic numbers, and explained how that approach could be used for many different coloring problems. Here, we follow this line of research for the particular case of acyclic coloring: we show that every graph with maximum degree Delta has acyclic chromatic number at most 3/2 Delta 4/3 + O(Delta). (C) 2019 Elsevier B.V. All rights reserved.

引用

页数：13

共 29 条

[1] Nonrepetitive colorings of graphs [J].

Alon, N ;

Grytczuk, J ;

Haluszcak, M ;

Riordan, O .

RANDOM STRUCTURES & ALGORITHMS, 2002, 21 (3-4) :336-346

[2] Acyclic edge colorings of graphs [J].

Alon, N ;

Sudakov, B ;

Zaks, A .

JOURNAL OF GRAPH THEORY, 2001, 37 (03) :157-167

[3] ACYCLIC COLORING OF GRAPHS [J].

ALON, N ;

MCDIARMID, C ;

REED, B .

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

[4]

Burstein Michael I., 1979, Soobshcheniya Akademii Nauk Gruzinskoi SSR, V93, P21

[5]

Dieng Y., 2010, P 8FCC

[6] NONREPETITIVE COLOURING VIA ENTROPY COMPRESSION [J].

Dujmovic, Vida ;

Joret, Gwenael ;

Kozik, Jakub ;

Wood, David R. .

COMBINATORICA, 2016, 36 (06) :661-686

[7]

Erdos L., 1973, and Finite Sets, V10, P609

[8] Acyclic edge-coloring using entropy compression [J].

Esperet, Louis ;

Parreau, Aline .

EUROPEAN JOURNAL OF COMBINATORICS, 2013, 34 (06) :1019-1027

[9] Star coloring of graphs [J].

Fertin, G ;

Raspaud, A ;

Reed, B .

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

[10] Acyclic coloring of graphs of maximum degree five: Nine colors are enough [J].

Fertin, Guillaume ;

Raspaud, Andre .

INFORMATION PROCESSING LETTERS, 2007, 105 (02) :65-72

← 1 2 3 →