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.
Belavadi et al. (Mon,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: