Paths between colourings of sparse graphs

DOI10.1016/J.EJC.2018.09.001zbMATH Open1400.05082arXiv1803.03950OpenAlexW2963190423MaRDI QIDQ1621073FDOQ1621073

Authors: Carl Feghali 

Publication date: 15 November 2018

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

Abstract: The reconfiguration graph $R_k(G)$ of the $k$-colourings of a graph~$G$ has as vertex set the set of all possible $k$-colourings of $G$ and two colourings are adjacent if they differ on exactly one vertex. We give a short proof of the following theorem of Bousquet and Perarnau (emph{European Journal of Combinatorics}, 2016). Let $d$ and $k$ be positive integers, $kgeqd+1$. For every $epsilon>0$ and every graph $G$ with $n$ vertices and maximum average degree $d-epsilon$, there exists a constant $c=c(d,epsilon)$ such that $R_k(G)$ has diameter $O(n^c)$. Our proof can be transformed into a simple polynomial time algorithm that finds a path between a given pair of colourings in $R_k(G)$.

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

Recommendations

• Reconfiguring colorings of graphs with bounded maximum average degree
• Paths between colourings of graphs with bounded tree-width
• On the diameter of reconfiguration graphs for vertex colourings
• A reconfigurations analogue of Brooks' theorem
• A polynomial version of Cereceda's conjecture

zbMATH Keywords

reconfiguration graph

Mathematics Subject Classification ID

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

Cites Work

• Mixing 3-colourings in bipartite graphs
• Connectedness of the graph of vertex-colourings
• Improved bounds for sampling colorings
• The complexity of change
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Recoloring graphs via tree decompositions
• Introduction to reconfiguration
• Fast recoloring of sparse graphs

Cited In (17)

• Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
• On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs
• Paths between colourings of graphs with bounded tree-width
• In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent
• Optimally reconfiguring list and correspondence colourings
• List-recoloring of sparse graphs
• Dominating sets reconfiguration under token sliding
• An update on reconfiguring 10-colorings of planar graphs
• Reconfiguring colorings of graphs with bounded maximum average degree
• Recoloring graphs of treewidth 2
• A reconfigurations analogue of Brooks' theorem
• Reconfiguring 10-colourings of planar graphs
• A polynomial version of Cereceda's conjecture
• On the connectivity of proper colorings of random graphs and hypergraphs
• Strengthening a Theorem of Meyniel
• Toward Cereceda's conjecture for planar graphs
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

This page was built for publication: Paths between colourings of sparse graphs

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