Acyclic, star and injective colouring: A complexity picture for H-free graphs
Jan Bok, Nikola Jedličková, Barnaby D. Martin, Pascal Ochem, Daniël Paulusma, Siani Smith · Journal of Computer and System Sciences · 2025
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.