2021/04/21 by Brause, Christoph, Golovach, Petr, Martin, Barnaby +3
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2104.10593
We examine the effect of bounding the diameter for 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≤ 2 but NP-complete if d≥ 4, and Star 3-Colouring is polynomial-time solvable if d≤ 3 but NP-complete for d≥ 8. As far as we are aware, Star 3-Colouring is the first problem that exhibits a complexity jump for some d≥ 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.