Reconfiguring colorings of graphs with bounded maximum average degree

DOI10.1016/J.JCTB.2020.11.001MaRDI QIDQ2222045zbMATH OpenOpenAlexFDO

Authors Carl Feghali

Publication date 3 February 2021

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

graph recoloringsparse graphs

Mathematics Subject Classification ID

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

Abstract: The reconfiguration graph $R_k(G)$ for the $k$-colorings of a graph $G$ has as vertex set the set of all possible $k$-colorings of $G$ and two colorings are adjacent if they differ in the color of exactly one vertex of $G$. Let $d,kgeq1$ be integers such that $kgeqd+1$. We prove that for every $epsilon>0$ and every graph $G$ with $n$ vertices and maximum average degree $d-epsilon$, $R_k(G)$ has diameter $O(n(logn{)}^{d-1})$. This significantly strengthens several existing results.

Recommendations

• Paths between colourings of sparse graphs
• On the diameter of reconfiguration graphs for vertex colourings
• An update on reconfiguring 10-colorings of planar graphs
• A reconfigurations analogue of Brooks' theorem and its consequences
• Toward Cereceda's conjecture for planar graphs

Cites work

• Fast recoloring of sparse graphs
• Paths between colourings of sparse graphs
• Reconfiguring 10-colourings of planar graphs
• Toward Cereceda's conjecture for planar graphs

Cited in

(18)

• Paths between colourings of sparse graphs
• Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph
• In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent
• List-recoloring of sparse graphs
• An update on reconfiguring 10-colorings of planar graphs
• Recoloring graphs of treewidth 2
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• On the diameter of reconfiguration graphs for vertex colourings
• A reconfigurations analogue of Brooks' theorem
• The complexity of changing colourings with bounded maximum degree
• Recoloring Planar Graphs of Girth at Least Five
• Optimally reconfiguring list and correspondence colourings
• 5‐Coloring reconfiguration of planar graphs with no short odd cycles
• Redicolouring digraphs: directed treewidth and cycle-degeneracy
• List recoloring of planar graphs
• 10-list recoloring of planar graphs
• Reconfiguration graphs for vertex colorings of P₅-free graphs
• List recoloring of planar graphs without 4-cycles

This page was built for publication: Reconfiguring colorings of graphs with bounded maximum average degree

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