Hardness transitions and uniqueness of acyclic colouring

For k is an element of N, a k-acyclic colouring of a graph G is a function f:V(G)->{0,1,& mldr;,k-1} such that (i) f(u) not equal f(v) for every edge uv of G, and (ii) there is no cycle in G bicoloured by f. For k is an element of N, the problem k-Acyclic Colourability takes a graph g as input and asks whether G admits a k-acyclic colouring. Ochem (EuroComb 2005) proved that 3-Acyclic Colourability is NP-complete for bipartite graphs of maximum degree 4. Mondal et al. (2013) proved that 4-Acyclic Colourability is NP-complete for graphs of maximum degree five. We prove that for k >= 3, k-Acyclic Colourability is NP-complete for bipartite graphs of maximum degree k+1, thereby generalising the NP-completeness result of Ochem, and adding bipartiteness to the NP-completeness result of Mondal et al.. In contrast, k-Acyclic Colourability is polynomial-time solvable for graphs of maximum degree at most 0.38k(3/4). Hence, for k >= 3, the least integer d such that k-Acyclic Colourability in graphs of maximum degree d is NP-complete, denoted by L-a((k)), satisfies 0.38 k(3/4)<L-a((k))) <= k+1. We prove that for k >= 4, k-Acyclic Colourability in d-regular graphs is NP-complete if and only if L-a((k)) <= d <= 2k-3. We also show that it is coNP-hard to check whether an input graph G admits a unique k-acyclic colouring up to colour swaps (resp. up to colour swaps and automorphisms).(c) 2023 Elsevier B.V. All rights reserved.