Decremental optimization of vertex-colouring under the reconfiguration framework. Issue 1 (2nd January 2023) - Yanagisawa, Yusuke; Suzuki, Akira; Tamura, Yuma; Zhou, Xiao
Abstract : Suppose that we are given a positive integer k, and a k -(vertex-)colouring f 0 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 f 0 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.