Reconfiguration of vertex colouring and forbidden induced subgraphs

DOI10.1016/j.ejc.2023.103908arXiv2206.09268OpenAlexW4389899308MaRDI QIDQ6201889

Manoj M. Belavadi, Owen Merkel, Kathie Cameron

Publication date: 26 March 2024

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

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

zbMATH Keywords

\(\ell\)-recolouring diameterreconfiguration graph of the \(k\)-colourings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Connectivity (05C40)

Cites Work

• Unnamed Item
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Paw-free graphs
• Reconfiguration in bounded bandwidth and tree-depth
• Recoloring graphs via tree decompositions
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• Recolouring weakly chordal graphs and the complement of triangle-free graphs
• Mixing colourings in \(2K_2\)-free graphs
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Connectedness of the graph of vertex-colourings