Recoloring via Modular Decomposition

ABSTRACT The reconfiguration graph of the ‐colorings of a graph , denoted , is the graph whose vertices are the ‐colorings of and two colorings are adjacent in if they differ in color on exactly one vertex. A graph is said to be recolorable if is connected for all . We demonstrate how to use the modular decomposition of a graph to prove that it is recolorable. In particular, we prove that every (, diamond)‐free graph, every (, house, bull)‐free graph, and every (, , co‐fork)‐free graph is recolorable. A graph is prime if it cannot be decomposed by modular decomposition except into single vertices. For a prime graph , we study the complexity of deciding if is ‐colorable and the complexity of deciding if there exists a path between two given ‐colorings in . Suppose is a hereditary class of graphs. We prove that if every blowup of every prime graph in is recolorable, then every graph in is recolorable.