  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. Hence, every injective colouring is a star colouring and every
star colouring is an acyclic colouring. The corresponding decision problems are
Acyclic Colouring, Star Colouring and Injective Colouring (the last problem is
also known as $L(1,1)$-Labelling). A classical complexity result on Colouring
is a well-known dichotomy for $H$-free graphs (a graph is $H$-free if it does
not contain $H$ as an induced subgraph). In contrast, there is no systematic
study into the computational complexity of Acyclic Colouring, Star Colouring
and Injective Colouring despite numerous algorithmic and structural results
that have appeared over the years. We perform such a study and 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.
