Decremental optimization of vertex-colouring under the reconfiguration framework. Issue 1 (2nd January 2023)

• Record Type: Journal Article
• Authors: Yanagisawa, Yusuke; Suzuki, Akira; Tamura, Yuma; Zhou, Xiao
• Is Part Of: International journal of computer mathematics. Volume 8:Issue 1(2023)
• Page Start: 80
• Page End: 92
• Publication Date: 2023-01-02
• Subjects: Combinatorial reconfiguration -- graph algorithms -- graph colouring -- linear-time algorithms; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2023.2185543
• Languages: English
• ISSNs: 2379-9927

Abstract

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.