Acyclic edge-coloring using entropy compression

Esperet, Louis; Parreau, Aline

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1016/j.ejc.2013.02.007

Titre :

Acyclic edge-coloring using entropy compression

Auteur(s) :

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

Titre de la revue :

European Journal of Combinatorics

Pagination :

1019-1027

Éditeur :

Elsevier

Date de publication :

2013

ISSN :

0195-6698

Discipline(s) HAL :

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

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :