2023/09/20 by A., Shalu M., Antony, Cyriac
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2309.11212
For k∈ ℕ, a k-acyclic colouring of a graph G is a function f\colon V(G)→ \0,1,…,k-1\ such that (i)~f(u)≠ f(v) for every edge uv of G, and (ii)~there is no cycle in G bicoloured by f. For k∈ ℕ, 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. (J. Discrete Algorithms, 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.38 k 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 La(k), satisfies 0.38 k 3/4