Fast recoloring of sparse graphs

DOI10.1016/J.EJC.2015.08.001MaRDI QIDQ896058zbMATH OpenOpenAlexFDO

Authors Nicolas Bousquet, Guillem Perarnau

Publication date 11 December 2015

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.6997

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Abstract: In this paper, we show that for every graph of maximum average degree bounded away from $d$, any $(d+1)$-coloring can be transformed into any other one within a polynomial number of vertex recolorings so that, at each step, the current coloring is proper. In particular, it implies that we can transform any $8$-coloring of a planar graph into any other $8$-coloring with a polynomial number of recolorings. These results give some evidence on a conjecture of Cereceda, van den Heuvel and Johnson which asserts that any $(d+2)$ coloring of a $d$-degenerate graph can be transformed into any other one using a polynomial number of recolorings. We also show that any $(2d+2)$-coloring of a $d$-degenerate graph can be transformed into any other one using a linear number of recolorings.

Recommendations

• List-recoloring of sparse graphs
• Recoloring Planar Graphs of Girth at Least Five
• A polynomial version of Cereceda's conjecture
• Recoloring graphs of treewidth 2
• Toward Cereceda's conjecture for planar graphs

Cites work

• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Mixing 3-colourings in bipartite graphs
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Recoloring graphs via tree decompositions
• Sparsity. Graphs, structures, and algorithms
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The complexity of bounded length graph recoloring and CSP reconfiguration

Cited in

(26)

• On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs
• Kempe equivalence of colourings of cubic graphs
• Kempe changes in degenerate graphs
• Digraph redicolouring
• Paths between colourings of sparse graphs
• Redicolouring digraphs: directed treewidth and cycle-degeneracy
• A reconfigurations analogue of Brooks' theorem and its consequences
• In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent
• Introduction to reconfiguration
• List-recoloring of sparse graphs
• A Thomassen-type method for planar graph recoloring
• Recoloring Planar Graphs of Girth at Least Five
• An update on reconfiguring 10-colorings of planar graphs
• Reconfiguring colorings of graphs with bounded maximum average degree
• Recoloring graphs of treewidth 2
• Reconfiguring 10-colourings of planar graphs
• A polynomial version of Cereceda's conjecture
• scientific article; zbMATH DE number 7525461 (Why is no real title available?)
• On the connectivity of proper colorings of random graphs and hypergraphs
• Recoloring graphs via tree decompositions
• Distributed recoloring
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• Kempe equivalence of colourings of cubic graphs
• List recoloring of planar graphs
• On a conjecture of Mohar concerning Kempe equivalence of regular graphs

This page was built for publication: Fast recoloring of sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896058)