Abstract
A set of vertices in a graph is ccolorable if the subgraph induced by the set has a proper ccoloring. In this paper, we study the problem of finding a stepbystep transformation (reconfiguration) between two ccolorable sets in the same graph. This problem generalizes the wellstudied Independent Set Reconfiguration problem. As the first step toward a systematic understanding of the complexity of this general problem, we study the problem on classes of perfect graphs. We first focus on interval graphs and give a combinatorial characterization of the distance between two ccolorable sets. This gives a lineartime algorithm for finding an actual shortest reconfiguration sequence for interval graphs. Since interval graphs are exactly the graphs that are simultaneously chordal and cocomparability, we then complement the positive result by showing that even deciding reachability is PSPACEcomplete for chordal graphs and for cocomparability graphs. The hardness for chordal graphs holds even for split graphs. We also consider the case where c is a fixed constant and show that in such a case the reachability problem is polynomialtime solvable for split graphs but still PSPACEcomplete for cocomparability graphs. The complexity of this case for chordal graphs remains unsettled. As byproducts, our positive results give the first polynomialtime solvable cases (split graphs and interval graphs) for Feedback Vertex Set Reconfiguration.
BibTeX  Entry
@InProceedings{ito_et_al:LIPIcs:2018:8853,
author = {Takehiro Ito and Yota Otachi},
title = {{Reconfiguration of Colorable Sets in Classes of Perfect Graphs}},
booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
pages = {27:127:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770682},
ISSN = {18688969},
year = {2018},
volume = {101},
editor = {David Eppstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8853},
URN = {urn:nbn:de:0030drops88539},
doi = {10.4230/LIPIcs.SWAT.2018.27},
annote = {Keywords: reconfiguration, colorable set, perfect graph}
}
Keywords: 

reconfiguration, colorable set, perfect graph 
Collection: 

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) 
Issue Date: 

2018 
Date of publication: 

04.06.2018 