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

• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• 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 complexity of bounded length graph recoloring and CSP reconfiguration
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Cited in

(35)

• Paths between colourings of sparse graphs
• Recoloring graphs via tree decompositions
• On a conjecture of Mohar concerning Kempe equivalence of regular graphs
• A Thomassen-type method for planar graph recoloring
• A polynomial version of Cereceda's conjecture
• In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent
• List-recoloring of sparse graphs
• Reconfiguring colorings of graphs with bounded maximum average degree
• An update on reconfiguring 10-colorings of planar graphs
• Recoloring graphs of treewidth 2
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• Introduction to reconfiguration
• Reconfiguring 10-colourings of planar graphs
• A reconfigurations analogue of Brooks' theorem and its consequences
• Linear transformations between colorings in chordal graphs
• Distributed recoloring
• On the connectivity of proper colorings of random graphs and hypergraphs
• On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs
• Recoloring Planar Graphs of Girth at Least Five
• Kempe equivalence of colourings of cubic graphs
• Kempe equivalence of colourings of cubic graphs
• Digraph redicolouring
• Kempe changes in degenerate graphs
• Redicolouring digraphs: directed treewidth and cycle-degeneracy
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• List recoloring of planar graphs
• Critically fixed Thurston maps: classification, recognition, and twisting
• Linear recoloring diameter of degenerate chordal graphs and bounded treewidth graphs
• Sharp bounds on lengths of linear recolouring sequences
• 10-list recoloring of planar graphs
• Independent set reconfiguration in H-free graphs
• Reconfiguration graphs for vertex colorings of P₅-free graphs
• Short and local transformations between ( +1)-colorings
• Optimal list recoloring of subcubic graphs and complete multipartite graphs
• List recoloring of planar graphs without 4-cycles

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)