Recoloring some hereditary graph classes

DOI10.1016/j.dam.2024.10.026MaRDI QIDQ6657243

Kathie Cameron, Manoj M. Belavadi

Publication date: 6 January 2025

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

reconfiguration graphforbidden induced subgraph\(k\)-coloring\(k\)-mixingfrozen coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Paw-free graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Reconfiguration in bounded bandwidth and tree-depth
• Recoloring graphs via tree decompositions
• Chromatic symmetric functions and \(H\)-free graphs
• 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
• Introduction to reconfiguration
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Reconfiguration of vertex colouring and forbidden induced subgraphs

This page was built for publication: Recoloring some hereditary graph classes