Entropy compression method applied to graph colorings

Daniel Gonçalves 1 Mickaël Montassier 1 Alexandre Pinlou 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Based on the algorithmic proof of Lov\'asz local lemma due to Moser and Tardos, Esperet and Parreau developed a framework to prove upper bounds for several chromatic numbers (in particular acyclic chromatic index, star chromatic number and Thue chromatic number) using the so-called \emph{entropy compression method}. Inspired by this work, we propose a more general framework and a better analysis. This leads to improved upper bounds on chromatic numbers and indices. In particular, every graph with maximum degree Δ has an acyclic chromatic number at most 32Δ43+O(Δ), and a non-repetitive chromatic number at most Δ2+1.89Δ53+O(Δ43). Also every planar graph with maximum degree Δ has a facial Thue chromatic number at most Δ+O(Δ12) and facial Thue chromatic index at most 10.
Type de document :
Communication dans un congrès
ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. 9th International colloquium on graph theory and combinatorics, June 30-July 4, 2014, 2014
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01233456
Contributeur : Alexandre Pinlou <>
Soumis le : mercredi 25 novembre 2015 - 11:21:25
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-01233456, version 1
  • ARXIV : 1406.4380

Collections

Citation

Daniel Gonçalves, Mickaël Montassier, Alexandre Pinlou. Entropy compression method applied to graph colorings. ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. 9th International colloquium on graph theory and combinatorics, June 30-July 4, 2014, 2014. 〈lirmm-01233456〉

Partager

Métriques

Consultations de la notice

62