Recoloring via Modular Decomposition

Authors:
Open Access
Publisher website
Google Scholar
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.
Funding Information
  • Natural Sciences and Engineering Research Council of Canada (RGPIN‐2016‐06517)

This publication has 16 references indexed in Scilit: