Web Survey on Combinatorial Reconfiguration

(back to home) (about this survey)

Filters:
Problems: Vertex coloring
Choose Problem

Authors: all
Choose Author


[2]
Bojan Mohar,
Kempe equivalence of colorings,
Proceedings of a Conference in Memory of Claude Berge, Graph Theory in Paris, pp. 287-297, 2006. (LINK)

[3]
Luis Cereceda, Jan van den Heuvel and Matthew Johnson,
Connectedness of the graph of vertex-colourings,
Discrete Mathematics 308(5-6), pp. 913-919, 2008. (LINK)

[4]
Paul S. Bonsma and Luis Cereceda,
Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances,
Theoretical Computer Science 410(50), pp. 5215-5226, 2009. (LINK)

[5]
Luis Cereceda, Jan van den Heuvel and Matthew Johnson,
Mixing 3-colourings in bipartite graphs,
European Journal of Combinatorics 30(7), pp. 1593-1606, 2009. (LINK)

[9]
Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel and Daniël Paulusma,
On the diameter of reconfiguration graphs for vertex colourings,
Proceedings of the 6th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2011), Electronic Notes in Discrete Mathematics 38, pp. 161-166, 2011. (LINK)

[10]
Luis Cereceda, Jan van den Heuvel and Matthew Johnson,
Finding paths between 3-colorings,
Journal of Graph Theory 67(1), pp. 69-82, 2011. (LINK)

[18]
Marthe Bonamy and Nicolas Bousquet,
Recoloring bounded treewidth graphs,
Proceedings of the 7th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2013), Electronic Notes in Discrete Mathematics 44, pp. 257-262, 2013. (LINK)

[22]
Marthe Bonamy and Nicolas Bousquet,
Recoloring graphs via tree decompositions,
arXiv 1403.6386, 2014. (LINK)

[23]
Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel and Daniël Paulusma,
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs,
Journal of Combinatorial Optimization 27(1), pp. 132-143, 2014. (LINK)

[25]
Paul S. Bonsma, Amer E. Mouawad, Naomi Nishimura and Venkatesh Raman,
The complexity of bounded length graph recoloring and CSP reconfiguration,
Proceedings of the 9th International Symposium on Parameterized and Exact Computation (IPEC 2014), Lecture Notes in Computer Science 8894, pp. 110-121, 2014. (LINK)

[31]
Marcin Wrochna,
Reconfiguration in bounded bandwidth and treedepth,
arXiv 1405.0847, 2014. (LINK)

[32]
Marthe Bonamy, Nicolas Bousquet, Carl Feghali and Matthew Johnson,
On a conjecture of Mohar concerning Kempe equivalence of regular graphs,
arXiv 1510.06964, 2015. (LINK)

[36]
Tatsuhiko Hatanaka, Takehiro Ito and Xiao Zhou,
The list coloring reconfiguration problem for bounded pathwidth graphs,
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E98-A(6), pp. 1168-1178, 2015. (LINK)

[39]
Daniel C. McDonald,
Connectedness and Hamiltonicity of graphs on vertex colorings,
arXiv 1507.05344, 2015. (LINK)

[43]
Julie Beier, Janet Fierson, Ruth Haas, Heather M. Russell and Kara Shavo,
Classifying coloring graphs,
Discrete Mathematics 339(8), pp. 2100-2112, 2016. (LINK)

[46]
Paul S. Bonsma and Daniël Paulusma,
Using contracted solution graphs for solving reconfiguration problems,
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Leibniz International Proceedings in Informatics 58, pp. 20:01-20:15, 2016. (LINK)

[47]
Nicolas Bousquet and Guillem Perarnau,
Fast recoloring of sparse graphs,
European Journal of Combinatorics 52(Part A), pp. 1-11, 2016. (LINK)

[49]
Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel and Daniël Paulusma,
Finding shortest paths between graph colourings,
Algorithmica 75(2), pp. 295-321, 2016. (LINK)

[59]
Carl Feghali, Matthew Johnson and Daniël Paulusma,
Kempe equivalence of colourings of cubic graphs,
European Journal of Combinatorics 59, pp. 1-10, 2017. (LINK)

[60]
Tatsuhiko Hatanaka, Takehiro Ito and Xiao Zhou,
Parameterized complexity of the list coloring reconfiguration problem with graph parameters,
arXiv 1705.07551, 2017. (LINK)