Decremental optimization of vertex-colouring under the reconfiguration framework

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.
   Google Scholar
• M. Bonamy and N. Bousquet, Recoloring graphs via tree decompositions, Eur. J. Comb. 69 (2018), pp. 200–213.
   Google Scholar
• 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.
   Google Scholar
• 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.
   Google Scholar
• 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.
   Google Scholar
• P.S. Bonsma and D. Paulusma, Using contracted solution graphs for solving reconfiguration problems, Acta Inform. 56 (2019), pp. 619–648.
   Google Scholar
• 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.
   Google Scholar
• L. Cereceda, J. van den Heuvel, and M. Johnson, Finding paths between 3-colourings, J. Graph Theory67 (1) (2011), pp. 69–82.
   Google Scholar
• C.A. Christen and S.M. Selkow, Some perfect coloring properties of graphs, J. Combin. Theory Ser. B 27 (1) (1979), pp. 49–59.
   Web of Science ®Google Scholar
• J. Erickson, Algorithms, 2019.
   Google Scholar
• 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.
   Google Scholar
• M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.
   Google Scholar
• 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.
   Google Scholar
• 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.
   Google Scholar
• 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.
   Google Scholar
• 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.
   Google Scholar
• 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.
   Google Scholar
• M. Johnson, D. Kratsch, S. Kratsch, V. Patel, and D. Paulusma, Finding shortest paths between graph colourings, Algorithmica 75 (2016), pp. 295–321.
   Google Scholar
• 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.
   Google Scholar
• S.E. Markossian, G.S. Gasparian, and B.A. Reed, β-perfect graphs, J. Combin. Theory Ser. B 67 (1) (1996), pp. 1–11.
   Google Scholar
• 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.
   Google Scholar
• N. Nishimura, Introduction to reconfiguration, Algorithms 11 (4) (2018), p. 52.
   Google Scholar
• 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.
   Google Scholar
• M. Wrochna, Reconfiguration in bounded bandwidth and treedepth, J. Comput. Syst. Sci. 93 (2018), pp. 1–10.
   Google Scholar