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.

An island in a graph is a set $X$ of vertices such that each element of $X$ has few neighbors outside $X$. In this paper, we prove several bounds on the size of islands in large graphs embeddable on fixed surfaces. As direct consequences of our results, we obtain the following: (1) Every graph of genus $g$ can be colored from lists of size 5, in such a way that each monochromatic component has size $O(g)$. Moreover, all but $O(g)$ vertices lie in monochromatic components of size at most 3. (2) Every triangle-free graph of genus $g$ can be colored from lists of size 3, in such a way that each monochromatic component has size $O(g)$. Moreover, all but $O(g)$ vertices lie in monochromatic components of size at most 10. (3) Every graph of girth at least 6 and genus $g$ can be colored from lists of size 2, in such a way that each monochromatic component has size $O(g)$. Moreover, all but $O(g)$ vertices lie in monochromatic components of size at most 16. While (2) is optimal up to the size of the components, we conjecture that the size of the lists can be decreased to 4 in (1), and the girth can be decreased to 5 in (3). We also study the complexity of minimizing the size of monochromatic components in 2-colorings of planar graphs.

An infinite square-free word w over the alphabet Σ3 = {0, 1, 2} is said to have a k-stem σ if |σ| = k and w = σw1 w2 $\dots$ where for each i, there exists a permutation πi of Σ3 which extended to a morphism gives wi = πi (σ). Harju proved that there