Decremental optimization of vertex-colouring under the reconfiguration framework
Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou · International Journal of Computer Mathematics Computer Systems Theory · 2023
Suppose that we are given a positive integer k, and a k-(vertex-)colouring f0 of a given graph G. Then we are asked to find a colouring of G using the minimum number of colours among colourings that are reachable from f0 by iteratively changing a colour assignment of exactly one vertex while maintaining the property of k-colourings. In this paper, we give linear-time algorithms to solve the problem for graphs of degeneracy at most two and for the case where k≤3. These results imply linear-time algorithms for series-parallel graphs and grid graphs. In addition, we give linear-time algorithms for chordal graphs and cographs. On the other hand, we show that, for any k≥4, this problem remains NP-hard for planar graphs with degeneracy three and maximum degree four. Thus, we obtain a complexity dichotomy for this problem with respect to the degeneracy of a graph and the number k of colours.