The Coloring Reconfiguration Problem on Specific Graph Classes

• Item type: SIG Technical Reports(1)
• 公開日: 2017-11-09
• タイトル: The Coloring Reconfiguration Problem on Specific Graph Classes
• タイトル / 言語: en
• タイトル: The Coloring Reconfiguration Problem on Specific Graph Classes
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Graduate School of Information Sciences, Tohoku University
• 著者所属: Graduate School of Information Sciences, Tohoku University
• 著者所属: Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University
• 著者名: Tatsuhiko, Hatanaka; Takehiro, Ito; Xiao, Zhou
• 著者名(英): Tatsuhiko, Hatanaka; Takehiro, Ito; Xiao, Zhou
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We study the problem of transforming one (vertex) k-coloring of a graph into another one by changing only one vertex color assignment at a time, while at all times maintaining a k-coloring, where k denotes the number of colors. This decision problem is known to be PSPACE-complete even for bipartite graphs and any fixed constant k ≥ 4. In this paper, we study the problem from the viewpoint of graph classes. We first show that the problem remains PSPACE-complete for chordal graphs even if the number of colors is a fixed constant. We then demonstrate that, even when the number of colors is a part of input, the problem is solvable in polynomial time for several graph classes, such as split graphs and trivially perfect graphs.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We study the problem of transforming one (vertex) k-coloring of a graph into another one by changing only one vertex color assignment at a time, while at all times maintaining a k-coloring, where k denotes the number of colors. This decision problem is known to be PSPACE-complete even for bipartite graphs and any fixed constant k ≥ 4. In this paper, we study the problem from the viewpoint of graph classes. We first show that the problem remains PSPACE-complete for chordal graphs even if the number of colors is a fixed constant. We then demonstrate that, even when the number of colors is a part of input, the problem is solvable in polynomial time for several graph classes, such as split graphs and trivially perfect graphs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2017-AL-165, 号 7, p. 1-5, 発行日 2017-11-09
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会