Art

J-GLOBAL ID：201702261209391224   Reference number：17A1913760

The Coloring Reconfiguration Problem on Specific Graph Classes

特殊なグラフクラスにおける彩色再構成問題

Author (3)： HATANAKA Tatsuhiko (Tohoku Univ., Sendai, JPN) ,  ITO Takehiro (Tohoku Univ., Sendai, JPN) ,  ZHOU Xiao (Tohoku Univ., Sendai, JPN)
Material： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
Volume： 117  Issue： 301(MSS2017 24-46)  Page： 23-27  Publication year： Nov. 09, 2017 
JST Material Number： S0532B  ISSN： 0913-5685  Document type： Proceedings
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *graph ,  *color problem ,  *reconstitution ,  algorithm ,  completeness ,  complete graph
Semi thesaurus term： polynomial time algorithm

JST classification (1)： Basics of graph theory  (IA02020S)

Reference (17)：

• Bonamy, M., Johnson, M., Lignos, I., Patel, V., Paulusma, D.: Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. J. Combinatorial Optimization, Vol.27, pp.132-143 (2014).
• Bonamy, M., Bousquet, N.: Recoloring bounded treewidth graphs. Electronic Notes in Discrete Mathematics, Vol.44, pp.257-262 (2013).
• Bonsma, P., Cereceda, L.: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoretical Computer Science, Vol.410, pp.5215-5226 (2009).
• Bonsma, P., Mouawad, A.E., Nishimura, N., Raman, V.: The complexity of bounded length graph recoloring and CSP reconfiguration. Proc. of IPEC 2014, LNCS 8894, pp.110-121 (2014).
• Bonsma, P., Paulusma, D.: Using contracted solution graphs for solving reconfiguration problems. Proc. of MFCS 2016, LIPIcs 58, pp.20:1-20:15 (2016).

Terms in the title (4)： グラフ ,  クラス ,  彩色 ,  再構成