Recoloring via modular decomposition

DOI10.1002/JGT.70005MaRDI QIDQ6850235zbMATH OpenFDO

Authors Manoj M. Belavadi, Kathie Cameron, Ni Luh Dewi Sintiari

Publication date 3 March 2026

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1002/JGT.70005

zbMATH Keywords

\(k\)-mixing\(P_5\)-free graphsmodular decompositionreconfiguration graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites work

• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Finding paths between 3-colourings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Mixing colourings in 2K₂-free graphs
• On semi-\(P_ 4\)-sparse graphs
• On the structure of (banner, odd hole)-free graphs
• Recoloring graphs via tree decompositions
• Recoloring some hereditary graph classes
• Recolouring weakly chordal graphs and the complement of triangle-free graphs
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Reconfiguration in bounded bandwidth and tree-depth
• Reconfiguration of vertex colouring and forbidden induced subgraphs

This page was built for publication: Recoloring via modular decomposition

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