Acyclic, star and injective colouring: A complexity picture for H-free graphs

Bok, Jan; Jedličková, Nikola; Martin, Barnaby; Ochem, Pascal; Paulusma, Daniël; Smith, Siani

Abstract

A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring. We give almost complete complexity classifications for Acyclic Colouring, Star Colouring and Injective Colouring on H-free graphs (for each of the problems, we have one open case). Moreover, we give full complexity classifications if the number of colours k is fixed, that is, not part of the input. From our study it follows that for fixed k, the three problems behave in the same way, but this is no longer true if k is part of the input. To obtain several of our results we prove stronger complexity results that in particular involve the girth of a graph and the class of line graphs of multigraphs.

Citation

Bok, J., Jedličková, N., Martin, B., Ochem, P., Paulusma, D., & Smith, S. (2025). Acyclic, star and injective colouring: A complexity picture for H-free graphs. Journal of Computer and System Sciences, 154, Article 103662. https://doi.org/10.1016/j.jcss.2025.103662

• Journal Article Type: Article
• Acceptance Date: Apr 24, 2025
• Online Publication Date: May 13, 2025
• Publication Date: 2025-12
• Deposit Date: Jun 6, 2025
• Publicly Available Date: Jun 6, 2025
• Journal: Journal of Computer and System Sciences
• Print ISSN: 0022-0000
• Electronic ISSN: 1090-2724
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 154
• Article Number: 103662
• DOI: https://doi.org/10.1016/j.jcss.2025.103662
• Public URL: https://durham-repository.worktribe.com/output/3967683