Acyclic, star, and injective colouring: bounding the diameter (Q5918693)

Summary: We examine the effect of bounding the diameter for a number of natural and well-studied variants of the colouring problem. A 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. The last problem is also known as \(L(1, 1)\)-Labelling and we also consider the framework of \(L(a, b)\)-Labelling. We prove a number of (almost-)complete complexity classifications. In particular, we show that for graphs of diameter at most \(d\), Acyclic \(3\)-Colouring is polynomial-time solvable if \(d\leqslant 2\) but NP-complete if \(d\geqslant 4\), and Star \(3\)-Colouring is polynomial-time solvable if \(d\leqslant 3\) but NP-complete for \(d\geqslant 8\). As far as we are aware, Star \(3\)-Colouring is the first problem that exhibits a complexity jump for some \(d\geqslant 3\). Our third main result is that \(L(1, 2)\)-Labelling is NP-complete for graphs of diameter \(2\); we relate the latter problem to a special case of Hamiltonian Path.