Art

J-GLOBAL ID：201402281671868960   Reference number：14A1500223

Reconfiguration of List Colorings in a Graph

グラフのリスト点彩色の遷移

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： 114  Issue： 238(COMP2014 25-31)  Page： 19-24  Publication year： Oct. 01, 2014 
JST Material Number： S0532B  ISSN： 0913-5685  Document type： Proceedings
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： algorithm ,  *coloring (phenomenon) ,  *state ,  computation theory ,  Time ,  reachability ,  *graph ,  graph algorithm ,  *transition
Semi thesaurus term： *coloring ,  polynomial time ,  reachability

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

Reference (25)：

• Bonamy, M., Johnson, M., Lignos, I., Patel, V., Paulusma, D.: Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. J. Combinatorial Optimization 27, pp. 132-143 (2014)
• Bonamy, M., Bousquet, N.: Recoloring bounded treewidth graphs. Electronic Notes in Discrete Mathematics 44, pp. 257-262(2013)
• Bonsma, P.: Rerouting shortest paths in planar graphs. Proc. of FSTTCS 2012, pp. 337-349 (2012)
• Bonsma, P.: The complexity of rerouting shortest paths. Theoretical Computer Science 510, pp.1-12(2013)
• Bonsma, P., Cereceda, L.: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoretical Computer Science 410, pp. 5215-5226 (2009)

Terms in the title (4)： グラフ ,  リスト ,  彩色 ,  遷移