Recoloring some hereditary graph classes

DOI10.1016/J.DAM.2024.10.026MaRDI QIDQ6657243zbMATH OpenFDO

Authors Manoj M. Belavadi, Kathie Cameron

Publication date 6 January 2025

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

Full work available at URL https://doi.org/10.1016/J.DAM.2024.10.026

zbMATH Keywords

\(k\)-coloring\(k\)-mixingforbidden induced subgraphfrozen coloringreconfiguration graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• Reconfiguration of vertex colouring and forbidden induced subgraphs
• Recolouring weakly chordal graphs and the complement of triangle-free graphs
• Mixing colourings in 2K₂-free graphs
• Complexity of coloring reconfiguration under recolorability constraints
• Recolouring homomorphisms to triangle-free reflexive graphs

Cites work

• A tree representation for \(P_ 4\)-sparse graphs
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Chromatic symmetric functions and \(H\)-free graphs
• Finding paths between 3-colourings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Introduction to reconfiguration
• Mixing colourings in 2K₂-free graphs
• Paw-free graphs
• Recoloring graphs via tree decompositions
• 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

Cited in

(5)

• Reconfiguration of vertex colouring and forbidden induced subgraphs
• Recoloring via modular decomposition
• Sharp bounds on lengths of linear recolouring sequences
• Frozen colourings in 2 K₂-free graphs
• List recoloring of planar graphs without 4-cycles

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

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