Acyclic, star, and injective colouring: bounding the diameter∗

Abstract

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\leq 2$ but NP-complete if $d\geq 4$, and STAR $3$-COLOURING is polynomial-time solvable if $d\leq 3$ but NP-complete for $d\geq 8.$ As far as we are aware, STAR $3$-COLOURING is the first problem that exhibits a complexity jump for some $d\geq 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.