References
- A. Blanché, H. Mizuta, P. Ouvrard, and A. Suzuki, Decremental optimization of dominating sets under the reconfiguration framework, in Proceedings of the 31st International Workshop on Combinatorial Algorithms (IWOCA 2020), Lecture Notes in Computer Science, Vol. 12126, 2019, pp. 69–82.
- M. Bonamy and N. Bousquet, Recoloring graphs via tree decompositions, Eur. J. Comb. 69 (2018), pp. 200–213.
- M. Bonamy, M. Johnson, I. Lignos, V. Patel, and D. Paulusma, Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, J. Comb. Optim. 27 (2014), pp. 132–143.
- P.S. Bonsma and L. Cereceda, Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, Theor. Comput. Sci. 410 (50) (2009), pp. 5215–5226.
- P.S. Bonsma, A.E. Mouawad, N. Nishimura, and V. Raman, The complexity of bounded length graph recoloring and CSP reconfiguration, in Proceedings of the Ninth International Symposium on Parameterized and Exact Computation (IPEC 2014), Lecture Notes in Computer Science, Vol. 8894, 2014, pp. 110–121.
- P.S. Bonsma and D. Paulusma, Using contracted solution graphs for solving reconfiguration problems, Acta Inform. 56 (2019), pp. 619–648.
- L. Cereceda, J. van den Heuvel, and M. Johnson, Connectedness of the graph of vertex-colourings, Discrete Math. 308 (5–6) (2008), pp. 913–919.
- L. Cereceda, J. van den Heuvel, and M. Johnson, Finding paths between 3-colourings, J. Graph Theory67 (1) (2011), pp. 69–82.
- C.A. Christen and S.M. Selkow, Some perfect coloring properties of graphs, J. Combin. Theory Ser. B 27 (1) (1979), pp. 49–59.
- J. Erickson, Algorithms, 2019.
- C. Feghali, M. Johnson, and D. Paulusma, A reconfigurations analogue of Brooks' theorem and its consequences, J. Graph Theory 83 (4) (2016), pp. 340–358.
- M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.
- T. Hatanaka, T. Ito, and X. Zhou, The coloring reconfiguration problem on specific graph classes, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E102.D (3) (2019), pp. 423–429.
- J. van den Heuvel, The complexity of change, in S.R. Blackburn, S. Gerke, and M. Wildon, eds., Surveys in Combinatorics, Volume 409: London Mathematical Society Lecture Note Series, Cambridge: Cambridge University Press, 2013, pp. 127–160.
- T. Ito, E.D. Demaine, N.J.A. Harvey, C.H. Papadimitriou, M. Sideri, R. Uehara, and Y. Uno, On the complexity of reconfiguration problems, Theor. Comput. Sci. 412 (12–14) (2011), pp. 1054–1065.
- T. Ito, H. Mizuta, N. Nishimura, and A. Suzuki, Incremental optimization of independent sets under the reconfiguration framework, in Proceedings of the 25th International Computing and Combinatorics Conference (COCOON 2019), Lecture Notes in Computer Science, Vol. 11653, 2019, pp. 313–324.
- T. Ito, H. Mizuta, N. Nishimura, and A. Suzuki, Incremental optimization of independent sets under the reconfiguration framework, J. Comb. Optim. 43(5) (2020), p. 1264–1279.
- M. Johnson, D. Kratsch, S. Kratsch, V. Patel, and D. Paulusma, Finding shortest paths between graph colourings, Algorithmica 75 (2016), pp. 295–321.
- R.M. Karp, Reducibility among combinatorial problems, in R.E. Miller, J.W. Thatcher, and J.D. Bohlinger, eds., Complexity of Computer Computations, Heidelberg: Springer, 1972, pp. 85–103.
- S.E. Markossian, G.S. Gasparian, and B.A. Reed, β-perfect graphs, J. Combin. Theory Ser. B 67 (1) (1996), pp. 1–11.
- C.M. Mynhardt and S. Nasserasr, Reconfiguration of colourings and dominating sets in graphs, in 50 Years of Combinatorics, Graph Theory, and Computing, Fan Chung, Ron Graham, Frederick Hoffman, Ronald C. Mullin, Leslie Hogben, and Douglas B. West, ed., Chapman and Hall/CRC, New York, 2019. pp. 171–191.
- N. Nishimura, Introduction to reconfiguration, Algorithms 11 (4) (2018), p. 52.
- D.J. Rose, R.E. Tarjan, and G.S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput. 5 (2) (1976), pp. 266–283.
- M. Wrochna, Reconfiguration in bounded bandwidth and treedepth, J. Comput. Syst. Sci. 93 (2018), pp. 1–10.