Fast recoloring of sparse graphs

DOI10.1016/J.EJC.2015.08.001zbMATH Open1327.05189arXiv1411.6997OpenAlexW2964083169MaRDI QIDQ896058FDOQ896058

Authors: Nicolas Bousquet, Guillem Perarnau 

Publication date: 11 December 2015

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

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
• Redicolouring digraphs: directed treewidth and cycle-degeneracy
• Paths between colourings of sparse graphs
• 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
• Title not available (Why is that?)
• A polynomial version of Cereceda's conjecture
• On the connectivity of proper colorings of random graphs and hypergraphs
• Distributed recoloring
• Recoloring graphs via tree decompositions
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• Kempe equivalence of colourings of cubic graphs
• List recoloring of planar graphs
• Reconfiguration graph for vertex colourings of weakly chordal 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)