Acyclic edge-coloring using entropy compression

Esperet, Louis; Parreau, Aline

Document type :

Article dans une revue scientifique: Article original

DOI :

10.1016/j.ejc.2013.02.007

Title :

Acyclic edge-coloring using entropy compression

Author(s) :

Esperet, Louis [Auteur]
Optimisation Combinatoire [G-SCOP_OC]
Parreau, Aline [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]

Journal title :

European Journal of Combinatorics

Pages :

1019-1027

Publisher :

Elsevier

Publication date :

2013

ISSN :

0195-6698

HAL domain(s) :

Informatique [cs]/Mathématique discrète [cs.DM]

English abstract : [en]

An edge-coloring of a graph G is acyclic if it is a proper edge-coloring of G and every cycle contains at least three colors. We prove that every graph with maximum degree Delta has an acyclic edge-coloring with at most 4 ...
Show more >An edge-coloring of a graph G is acyclic if it is a proper edge-coloring of G and every cycle contains at least three colors. We prove that every graph with maximum degree Delta has an acyclic edge-coloring with at most 4 Delta - 4 colors, improving the previous bound of 9.62 (Delta - 1). Our bound results from the analysis of a very simple randomised procedure using the so-called entropy compression method. We show that the expected running time of the procedure is O(mn Delta^2 log Delta), where n and m are the number of vertices and edges of G. Such a randomised procedure running in expected polynomial time was only known to exist in the case where at least 16 Delta colors were available. Our aim here is to make a pedagogic tutorial on how to use these ideas to analyse a broad range of graph coloring problems. As an application, also show that every graph with maximum degree Delta has a star coloring with 2 sqrt(2) Delta^{3/2} + Delta colors.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :