30
Views
0
CrossRef citations to date
0
Altmetric
27th International Computing and Combinatorics Conference (Selected Papers from COCOON 2021)

Decremental optimization of vertex-colouring under the reconfiguration framework

, , &
Pages 80-92 | Received 25 Feb 2022, Accepted 12 Dec 2022, Published online: 02 Apr 2023
 

Abstract

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 k3. 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 k4, 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.

Acknowledgments

We are grateful to Tatsuhiko Hatanaka, Takehiro Ito and Haruka Mizuta for valuable discussions with them. We thank the anonymous referees for their constructive suggestions and comments.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

Akira Suzuki was partially supported by JSPS KAKENHI [grant numbers JP18H04091, JP20K11666 and JP20H05794], Japan. Yuma Tamura was partially supported by JSPS KAKENHI [grant number JP21K21278], Japan. Xiao Zhou was partially supported by JSPS KAKENHI [grant number JP19K11813], Japan.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.