# Hardness Transitions and Uniqueness of Acyclic Colouring

Shalu M.A., and Cyriac Antony
Indian Institute of Information Technology, Design & Manufacturing
(IIITDM) Kancheepuram, Chennai, India

###### Abstract

For $k\in\mathbb{N}$, a $k$-acyclic colouring of a graph $G$ is a function
$f\colon V(G)\to\\{0,1,\dots,k-1\\}$ such that (i) $f(u)\neq f(v)$ for every
edge $uv$ of $G$, and (ii) there is no cycle in $G$ bicoloured by $f$. For
$k\in\mathbb{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. (J. Discrete Algorithms, 2013) proved that
4-Acyclic Colourability is NP-complete for graphs of maximum degree five. We
prove that for $k\geq 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\geq 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)}\leq k+1$. We prove that for $k\geq 4$,
$k$-Acyclic Colourability in $d$-regular graphs is NP-complete if and only if
$L_{a}^{(k)}\leq d\leq 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).

##  1 Introduction and Definitions

Acyclic colouring is a variant of graph colouring introduced by Grünbaum [35]
and widely studied for the class of planar graphs [35, 12] and its
superclasses, such as 1-planar graphs [15, 62] and graphs embeddable on
surfaces [1, 4, 39]. An acyclic colouring of a graph $G$ is a (vertex)
colouring of $G$ without bicoloured cycles. It is used in the estimation of
sparse Hessian matrices [31]. The algorithmic complexity of acyclic colouring
is studied in various graph classes [6, 2, 60, 47, 46, 25, 9]. Brause et al.
[16] investigated the complexity of 3-acyclic colouring with respect to the
graph diameter. For $k\geq 3$, we study the complexity of $k$-acyclic
colouring with respect to the maximum degree of the graph focusing on graphs
of maximum degree $d$ and $d$-regular graphs. Our interest is in the values of
$d$ for which the complexity of $k$-acyclic colouring in graphs of maximum
degree $d$ (resp. $d$-regular graphs) differ drastically from that in graphs
of maximum degree $d-1$ (resp. $(d-1)$-regular graphs); we call such values of
$d$ as _hardness transitions_ of $k$-acyclic colouring (with respect to the
maximum degree) in the class of graphs of maximum degree $d$ (resp.
$d$-regular graphs); see Section 1.3 for details. We also prove computational
hardness results on unique acyclic colouring (see Section 1.4).

The paper is organised as follows. See Subsection 1.1 for basic definitions.
Subsection 1.2 discusses known results on the algorithmic complexity of
acyclic colouring, and Subsections 1.3 and 1.4 introduce the conventions and
notations we use related to hardness transitions and unique solution problems,
respectively. Subsection 1.5 lists the major contributions of this paper.
Section 2 presents our results on the hardness transitions of acyclic
colouring (with respect to the maximum degree). Section 3 discusses our
results on unique acyclic colouring. We conclude with Section 4 on open
problems.

###  1.1 Basic Definitions

All graphs considered in this paper are finite, simple and undirected. We
follow West [61] for graph theory terminology and notation. When the graph is
clear from the context, we denote the number of edges of the graph by $m$ and
the number of vertices by $n$. For a graph $G$, we denote the maximum degree
of $G$ by $\Delta(G)$. For a subset $S$ of the vertex set of $G$, the
_subgraph of $G$ induced by $S$_ is denoted by $G[S]$. The _girth_ of a graph
with a cycle is the length of its shortest cycle. A graph $G$ is _$2$
-degenerate_ if there exists a left-to-right ordering of its vertices such
that every vertex has at most two neighbours to its left. The _maximum average
degree_ $\text{mad}(G)$ of a graph $G$ is the maximum over average degrees of
subgraphs of $G$. That is, $\text{mad}(G)=\max\\{2|E(H)|/|V(H)|\colon H\text{
is a subgraph of }G\\}$. The treewidth of $G$ is denoted as $\text{tw}(G)$. A
3-regular graph is also called a _cubic graph_ , and a graph of maximum degree
3 is called a _subcubic graph_.

012012

(a)

012120

(b)

Figure 1: (a) a 3-colouring of a graph, which is not a 3-acyclic colouring
(bicoloured cycle highlighted), and (b) a 3-acyclic colouring of the circular
ladder graph $CL_{3}$ (which is not 3-star colourable).

A $k$-colouring of a graph $G$ is a function $f$ from the vertex set of $G$ to
a set of $k$ colours, say $\\{0,1,\dots,k-1\\}$, such that $f$ maps every pair
of adjacent vertices to different colours. Let us denote the $i$th colour
class $f^{-1}(i)$ by $V_{i}$. A $k$-acyclic colouring of $G$ is a
$k$-colouring $f$ of $G$ such that every pair of colour classes induces an
acyclic subgraph (i.e., $G[V_{i}\cup V_{j}]$ is a forest for every pair of
colour classes $V_{i}$ and $V_{j}$). See Figure 1 for an example. The _acyclic
chromatic number_ $\chi_{a}(G)$ of a graph $G$ is the least integer $k$ such
that $G$ is $k$-acyclic colourable. The problem Acyclic Colourability takes a
graph $G$ and a positive integer $k$ as input and asks whether $G$ is
$k$-acyclic colourable. For $k\in\mathbb{N}$, the decision problem
$k$-Colourability takes a graph $G$ as input and asks whether $G$ is
$k$-colourable. Similarly, for $k\in\mathbb{N}$, the problem $k$-Acyclic
Colourability takes a graph $G$ as input and asks whether $G$ is $k$-acyclic
colourable. To denote the restriction of a decision problem, we write the
conditions in parenthesis. For instance, $4$-Acyclic
Colourability$(\text{bipartite},\Delta=5)$ denotes the problem $4$-Acyclic
Colourability restricted to the class of bipartite graphs $G$ with
$\Delta(G)=5$. The Exponential Time Hypothesis (ETH) asserts that 3-Sat cannot
be solved in $2^{o(n)}$ time, where $n$ is the number of variables in the
3-Sat formula [53].

An _automorphism_ of a graph $G$ is a bijective function $\psi\colon V(G)\to
V(G)$ such that $xy\in E(G)$ if and only if $\psi(x)\psi(y)\in E(G)$. We say
that two colourings $f_{1}$ and $f_{2}$ of $G$ are the same _up to colour
swaps_ if $f_{2}$ can be obtained from $f_{1}$ by merely swapping colours
(that is, there exists a permutation $\sigma$ of colours such that
$f_{2}(v)=\sigma(f_{1}(v))$ for every vertex $v$ of $G$). We say that two
colourings $f_{1}$ and $f_{2}$ of $G$ are the same _up to colour swaps and
automorphisms_ if there exists a permutation $\sigma$ of colours and an
automorphism $\psi$ of $G$ such that $f_{2}(\psi(v))=\sigma(f_{1}(v))$ for
every vertex $v$ of $G$.

###  1.2 Acyclic colouring: Literature Survey

Grünbaum [35] conjectured that every planar graph is 5-acyclic colourable.
This conjecture and its proof by Borodin [12] attracted the attention of many,
and as a result, acyclic colouring is widely studied for the class of planar
graphs [13, Section 9] and its superclasses including 1-planar graphs [15, 62]
and graphs embeddable on surfaces [1, 4, 39]. It is also studied for other
graph classes such as regular graphs [6], line graphs [2, 60, 47], $H$-free
graphs for fixed $H$ [9], co-bipartite graphs [9]111See also
http://www.math.tau.ac.il/~nogaa/PDFS/multitaskadd.pdf, cographs [46], and
grid graphs [25]. Besides, acyclic colouring is studied for classes of graphs
obtained by imposing bounds on parameters such as maximum degree, girth,
maximum average degree and degeneracy [3, 42, 37, 18, 51, 14, 8]. Grünbaum
[35] proved that every graph of maximum degree 3 is 4-acyclic colourable.
Burstein [17] proved that every graph of maximum degree 4 is 5-acyclic
colourable. Due to the vast literature, we focus on the algorithmic complexity
aspect of acyclic colouring. For surveys, see [36, Section 3.11] and [13,
Section 9].

Fertin et al. [25] proved that $\chi_{a}(G)>1+\frac{m}{n}$ for every non-empty
graph $G$. Alon et al. [3] proved that $\chi_{a}(G)\leq 50\,d^{4/3}$ for every
graph $G$ of maximum degree $d$. This bound was improved by Ndreca et al. [52]
to $6.59\,d^{4/3}+3.3\,d$, and by Sereni and Volec [57] to $2.835\,d^{4/3}+d$.
See [33, 40, 5] for related work.

#### Algorithms for Acyclic Colouring

Every $k$-colouring of a chordal graph $G$ is a $k$-acyclic colouring of $G$,
and hence the acyclic chromatic number of $G$ can be computed in polynomial
time [30]. Lyons [46] proved that the acyclic chromatic number of a cograph
can be computed in linear time (i.e., $O(m+n)$ time). Linhares-Sales et al.
[45] designed a linear-time algorithm to compute the acyclic chromatic number
for two superclasses of cographs called $P_{4}$-tidy graphs and
$(q,q-4)$-graphs (for each fixed $q$). Skulrattanakulchai [59] designed a
linear-time algorithm to acyclic colour a graph of maximum degree 3 with 4
colours. Cheng et al. [19] designed a polynomial-time algorithm to obtain
optimal acyclic colourings of claw-free graphs of maximum degree 3.

#### Hardness Results on Acyclic Colouring

Kostochka [41] and Coleman and Cai [20] independently produced constructions
that proved the NP-completeness of Acyclic Colourability. We restate the
construction of Coleman and Cai [20] in Section 1.2 (see Construction 1). From
Construction 1, it follows that (i) for all $k\geq 3$, $k$-Acyclic
Colourability is NP-complete for 2-degenerate bipartite graphs and (ii)
$3$-Acyclic Colourability is NP-complete for 2-degenerate planar bipartite
graphs. Borrowing ideas from Construction 1, Gebremedhin et al. [29] proved
that for all $\epsilon>0$, it is NP-hard to approximate the acyclic chromatic
number of a 2-degenerate bipartite graph within $n^{\frac{1}{3}-\epsilon}$. In
contrast, every 2-degenerate graph admits an acyclic colouring with
$n^{\frac{1}{2}}$ colours [38, Theorem 6.2] (note that every unique superior
colouring is an acyclic colouring [38]); hence, the acyclic chromatic number
of a 2-degenerate graph is approximable within $n^{\frac{1}{2}}$. Bok et al.
[10] studied the complexity of Acyclic Colourability and $k$-Acyclic
Colourability in $H$-free graphs. They also proved that for $k\geq 3$,
$k$-Acyclic Colourability is NP-complete for line graphs and graphs of
arbitrarily large girth.

As mentioned, 3-Acyclic Colourability is NP-complete for 2-degenerate planar
bipartite graphs [20]. Ochem [54] proved that the problem remains NP-complete
when further restricted to graphs of maximum degree four. Alon and Zaks [2]
proved that 3-Acyclic Colourability is NP-complete for line graphs of subcubic
graphs. Mondal et al. [50] proved that 4-Acyclic Colourability is NP-complete
for graphs of maximum degree five. The problem 4-Acyclic Colourability is also
NP-complete for planar graphs of maximum degree seven [50] and 2-degenerate
planar bipartite graphs of maximum degree eight [54].

Consider a fixed $k\geq 3$. Emden-Weinert et al. [24] proved that
$k$-Colourability is NP-complete for graphs of maximum degree
$k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}}$.
Since the Construction of Coleman and Cai [20] (restated below as Construction
1) establishes a reduction from $k$-Colourability in graphs of maximum degree
$k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}}$ to
$k$-Acyclic Colourability in graphs of maximum degree
$k(k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}})$,
the latter problem is NP-complete as well.

######  Observation 1.

For $k\geq 3$, $k$-Acyclic Colourability is NP-complete for graphs of maximum
degree
$k(k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}})$.
∎

#### Fixed-Parameter Tractability of Acyclic Colouring

For every positive integer $k$, $k$-Acyclic Colourability can be expressed in
Monadic Second Order (MSO) logic without edge set quantifiers (i.e., MSO1) as
follows.

$\exists V_{0}\ \exists V_{1}\ \dots\exists V_{k-1}\
k\text{-Colouring}(V_{0},V_{1},\dots,V_{k-1})\ \wedge$
$\neg\text{ContainCycle}(V_{0},V_{1})\ \wedge\ \dots\wedge\
\neg\text{ContainCycle}(V_{k-2},V_{k-1})$

Here, ContainCycle$(V_{i},V_{j})$ stands for $\exists W\ \forall w\in W\ (w\in
V_{i}\vee w\in V_{j})\ \wedge\ (\exists w^{\prime}\ \exists w^{\prime\prime}\
\allowbreak\mbox{$w^{\prime}\in W$}\wedge\mbox{$w^{\prime\prime}\in W$}\wedge
w^{\prime}\neq
w^{\prime\prime}\wedge\text{adj}(w,w^{\prime})\wedge\text{adj}(w,w^{\prime\prime}))$
(that is, there exists a set $W\subseteq V_{i}\cup V_{j}$ such that every
vertex $w$ in $W$ has two neighbours $w^{\prime}$ and $w^{\prime\prime}$ in
$W$). Also, $k$-Colouring($V_{0},V_{1},\dots,V_{k-1}$) denotes the MSO formula
that says $\\{V_{0},V_{1},\dots,V_{k-1}\\}$ is a partition of the vertex set
of the graph into independent sets (see Section 1 in the supplementary
material for the MSO formula).

Therefore, for each $k$, the problem $k$-Acyclic Colourability admits FPT
algorithms with parameter either treewidth or cliquewidth by Courcelle’s
theorem [11, 21]. Ganian and Hliněný [27] obtained an FPT algorithm for
$k$-Acyclic Colourability with parameter rankwidth.

On the negative side, the following construction shows that unless coNP
$\subseteq$ NP/poly, $k$-Acyclic Colourability parameterized by treewidth does
not admit a polynomial kernel, provided $k\geq 3$.

###### Construction 1 (Coleman and Cai [20]).

_Parameter:_ An integer $k\geq 3$.
_Input:_ A graph $G$.
_Output:_ A 2-degenerate bipartite graph $G^{\prime}$.
_Guarantee 1_ [20] : $G$ is $k$-colourable if and only if $G^{\prime}$ is
$k$-acyclic colourable.
_Guarantee 2:_ $\text{tw}(G^{\prime})\leq\text{tw}(G)+1$.
_Steps:_
Replace each edge $e=uv$ of $G$ by a copy of the complete bipartite graph
$K_{2,k}$ with parts $\\{u,v\\}$ and $\\{e_{1},e_{2},\dots,e_{k}\\}$, where
$e_{1},e_{2},\dots,e_{k}$ are newly introduced vertices. To obtain a
2-degenerate ordering of $V(G^{\prime})$, list members of $V(G)$ followed by
the new vertices $e_{i}$.

Guarantee 2 is easy to prove, especially using the game-theoretic definition
of treewidth (see Section 2 in the supplementary material for details). By
Guarantee 2, the transformation from $k$-Colourability to $k$-Acyclic
Colourability established by Construction 1 is a Polynomial Parameter
Transformation (PPT) [26] when both problems are parameterized by treewidth.
Thus, we have the following theorem since $k$-Colourability with parameter
treewidth does not admit a polynomial kernel for $k\geq 3$.

######  Theorem 1.

For all $k\geq 3$, $k$-Acyclic Colourability parameterized by treewidth does
not admit a polynomial kernel unless coNP $\subseteq$ NP/poly. ∎

###  1.3 Hardness Transitions

Analysing the boundary between easy (i.e., polynomial-time solvable) and hard
(e.g., NP-complete) problems is a common theme in complexity theory [28].
Studying the change in the complexity of a problem in response to a change in
a single parameter falls in this category. Brause et al. [16] studied the
complexity of 3-Acyclic Colourability with the diameter of the graph as the
parameter. For $k\geq 3$, we study the complexity of $k$-acyclic colouring
with the maximum degree of the graph as the parameter. Recall that we write
the conditions in parenthesis to denote the restriction of a decision problem;
e.g.: $4$-Acyclic Colourability$(\text{bipartite},\Delta=5)$ denotes the
problem $4$-Acyclic Colourability restricted to the class of bipartite graphs
$G$ with $\Delta(G)=5$. We assume P $\neq$ NP throughout this paper; thus, NP
is partitioned into three classes: P, NPC and NPI [43]. We emphasise that our
interest is in the classification of NP-problems with respect to the P vs. NPC
vs. NPI trichotomy: that is, the complexity classes dealt with in this paper
are only P, NPC and NPI.

A decision problem $\Pi$ in NP has a _hardness transition_ with respect to a
discrete parameter $d$ at a point $d=x$ if $\Pi(d=x)$ and $\Pi(d=x-1)$ belong
to different complexity classes among P, NPC and NPI (e.g.: $\Pi(d=x)\in$ NPC
whereas $\Pi(d=x-1)\in$ P; see [48] for a discussion). For example,
3-Colourability of a graph of maximum degree $d$ is polynomial-time solvable
for $d=3$ (due to Brook’s theorem) and NP-complete for $d=4$ [28]. That is,
3-Colourability$(\Delta=3)\in$ P and 3-Colourability$(\Delta=4)\in$ NPC.
Hence, 3-Colourability has a hardness transition with respect to the maximum
degree $d$ at the point $d=4$. Note that each hardness transition presumably
deals with the P vs. NPC boundary since no ‘natural’ problem is known to be
NP-intermediate [7].

The number of hardness transitions depends on the problem as well as the
parameter under consideration. Interestingly, a decision problem can have
infinitely many hardness transitions. Cseh and Kavitha [22] proved that the
popular matching problem on complete graph $K_{n}$ is in P for odd $n$ whereas
it is NP-complete for even $n$. Therefore, the popular matching problem on
complete graph with respect to the number of vertices $n$ has infinitely many
hardness transitions.

Let us consider the complexity of $k$-colouring and $k$-acyclic colouring in
bounded degree graphs for fixed $k\geq 3$. Emden-Weinert et al. [24] proved
that $k$-Colourability is NP-complete for graphs of maximum degree
$k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}}$. By
Observation 1, $k$-Acyclic Colourability is NP-complete for graphs of maximum
degree
$k(k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}})$.
Hence, $k$-Colourability (resp. $k$-Acyclic Colourability) in graphs of
maximum degree $d$ is NP-complete when $d$ is sufficiently large. Observe that
if $k$-Colourability is NP-complete for graphs of maximum degree $d$, then it
is NP-complete for graphs of maximum degree $d+1$ (to produce a reduction, it
suffices to add a disjoint copy of $K_{1,d+1}$). This suggests the following
problem.

######  Problem 1.

For $k\geq 3$, what is the least integer $d$ such that $k$-Colourability is
NP-complete for graphs of maximum degree $d$?

Observe that Problem 1 deals with locating a point of hardness transition. By
the same argument as in $k$-Colourability, if $k$-Acyclic Colourability is NP-
complete for graphs of maximum degree $d$, then $k$-Acyclic Colourability is
NP-complete for graphs of maximum degree $d+1$. Therefore, for each $k\geq 3$,
there exists a unique integer $d^{*}$ such that $k$-Colourability (resp.
$k$-Acyclic Colourability) in graphs of maximum degree $d$ is NP-complete if
and only if $d\geq d^{*}$. Thus, one can ask the counterpart of Problem 1 for
acyclic colouring. Let $L^{(k)}$ and $L_{a}^{(k)}$ denote the answers to
Problem 1 and its counterpart for acyclic colouring; that is, $L^{(k)}$ (resp.
$L_{a}^{(k)}$) is the least integer $d$ such that $k$-Colourability (resp.
$k$-Acyclic Colourability) is NP-complete for graphs of maximum degree $d$.

Due to Brook’s theorem, $k$-Colourability is polynomial-time solvable for
graphs of maximum degree $k$, and thus $L^{(k)}\geq k+1$. For $k\geq 3$,
$k$-Colourability is NP-complete for graphs of maximum degree
$k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}}$
[24], and thus $k+1\leq L^{(k)}\leq
k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}}$.
Hence, $L^{(3)}=4$, $L^{(4)}=5$, $6\leq L^{(5)}\leq 7$, and so on. For
sufficiently large $k$ and
$d<k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}}$,
the problem $k$-Colourability is in P for graphs of maximum degree $d$ [49,
Theorem 43]. Therefore,
$L^{(k)}=k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}}$
for sufficiently large $k$. Yet, the exact value of $L^{(k)}$ is unknown for
small values of $k$ such as $k=5$ eventhough we know that
$L^{(5)}\in\\{6,7\\}$ (the complexity of 5-Colourability in graphs of maximum
degree 6 is open [56]).

###  1.4 Unique Solution Problems

For a decision problem $X$, the _unique solution problem_ associated with $X$
takes the same input as $X$ and asks whether problem $X$ with the given input
has exactly one solution. For instance, the unique solution problem associated
with Sat takes a boolean formula $B$ as input and asks whether $B$ has exactly
one satisfying truth assignment. For some decision problems, it is more
natural to consider an equivalence relation and ask whether there is only one
equivalence class in it. For example, for a graph $G$, it is customary to call
a $k$-colouring $f$ of $G$ as the unique $k$-colouring of $G$ if each
$k$-colouring of $G$ can be obtained from $f$ by merely swapping colours. That
is, instead of the number of $k$-colourings of $G$, we are interested in the
number of equivalence classes under $\mathcal{R}_{\text{swap}}(G,k)$ where
$\mathcal{R}_{\text{swap}}(G,k)$ is an equivalence relation on the set of
$k$-colourings of $G$ defined as
$(f_{1},f_{2})\in\mathcal{R}_{\text{swap}}(G,k)$ if $f_{1}$ and $f_{2}$ are
the same up to colour swaps. Similarly, we define an equivalence relation
$\mathcal{R}_{\text{swap+auto}}(G,k)$ on the set of $k$-colourings of $G$ as
$(f_{1},f_{2})\in\mathcal{R}_{\text{swap+auto}}(G,k)$ if $f_{1}$ and $f_{2}$
are the same up to colour swaps and automorphisms. Thus, we have two unique
solution problems associated with $k$-colouring.

Unique $k$-Colouring [$\mathcal{R}_{\text{swap}}$]
_Instance:_ A graph $G$.
_Question:_ Is the number of equivalence classes under
$\mathcal{R}_{\text{swap}}(G,k)$ exactly one?
_Question:_ (i.e., Is the number of $k$-colourings of $G$ up to colour swaps
exactly one?)

Unique $k$-Colouring [$\mathcal{R}_{\text{swap+auto}}$]
_Instance:_ A graph $G$.
_Question:_ Is the number of equivalence classes under
$\mathcal{R}_{\text{swap+auto}}(G,k)$ exactly one?
_Question:_ (Is the number of $k$-colourings of $G$ up to colour swaps and
automorphisms exactly one?)

An _another solution problem_ is closely related to the unique solution
problem. The another solution problem associated with Sat takes a boolean
formula $B$ and a satisfying truth assignment of $B$ as input and asks whether
$B$ has another satisfying truth assignment. Similar to the unique solution
problem, there are two another solution problems associated with
$k$-colouring, namely Another $k$-Colouring [$\mathcal{R}_{\text{swap}}$] and
Another $k$-Colouring [$\mathcal{R}_{\text{swap+auto}}$]. The former is
defined below, and the latter is defined likewise.

Another $k$-Colouring [$\mathcal{R}_{\text{swap}}$]
_Instance:_ A graph $G$, and a $k$-colouring $f$ of $G$.
_Question:_ Is there another $k$-colouring of $G$ up to colour swaps?
_Question:_ (i.e., a $k$-colouring $f^{*}$ of $G$ such that
$(f,f^{*})\notin\mathcal{R}_{\text{swap}}(G,k)$)

Dailey [23] proved that for all $k\geq 3$, Another $k$-Colouring
[$\mathcal{R}_{\text{swap}}$] is NP-hard. Hence, given a $k$-colourable graph
$G$, it is coNP-hard to check whether $G$ is uniquely $k$-colourable up to
colour swaps. That is, Unique $k$-Colouring [$\mathcal{R}_{\text{swap}}$] is
coNP-hard even when restricted to the class of $k$-colourable graphs. Dailey
[23] produced a reduction from $k$-Colourability to Another $k$-Colouring
[$\mathcal{R}_{\text{swap}}$]. A close look reveals that the same construction
also establishes a reduction from $k$-Colourability to Another $k$-Colouring
[$\mathcal{R}_{\text{swap+auto}}$]. Thus, for all $k\geq 3$, problems Another
$k$-Colouring [$\mathcal{R}_{\text{swap}}$] and Another $k$-Colouring
[$\mathcal{R}_{\text{swap+auto}}$] are NP-complete. As a result, the problems
Unique $k$-Colouring [$\mathcal{R}_{\text{swap}}$] and Unique $k$-Colouring
[$\mathcal{R}_{\text{swap+auto}}$] are coNP-hard for $k\geq 3$.

It is easy to observe that Dailey’s construction provides reductions from
$k$-Colourability($\Delta=k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}}$)
to Another $k$-Colouring [$\mathcal{R}_{\text{swap}}$]
($\Delta=(k-1)(k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}})$)
and to Another $k$-Colouring [$\mathcal{R}_{\text{swap+auto}}$]
($\Delta=(k-1)(k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}})$).
In particular, Another 3-Colouring [$\mathcal{R}_{\text{swap}}$] and Another
3-Colouring [$\mathcal{R}_{\text{swap+auto}}$] are NP-complete for graphs of
maximum degree 8.

We establish hardness results for unique solution problems and another
solution problems associated with acyclic colouring. These problems are
defined in the obvious way. For instance, Unique $k$-Acyclic Colouring
[$\mathcal{R}_{\text{swap}}$] is defined like Unique $k$-Colouring
[$\mathcal{R}_{\text{swap}}$].

###  1.5 Our Results

Recall that for $k\geq 3$, $L_{a}^{(k)}$ is the the least integer $d$ such
that $k$-Acyclic Colourability is NP-complete for graphs of maximum degree
$d$. For $k\geq 3$, $k$-Acyclic Colourability is NP-complete for graphs of
maximum degree
$k(k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}})$
by Observation 1, and thus $L_{a}^{(k)}\leq
k(k-1+\raisebox{1.5pt}{\big{\lceil}}\sqrt{k}\raisebox{1.5pt}{\big{\rceil}})$.
Ochem [54] proved that 3-Acyclic Colourability is NP-complete for bipartite
graphs of maximum degree 4; thus, $L_{a}^{(3)}\leq 4$. We generalise this
result: for $k\geq 3$, $k$-Acyclic Colourability is NP-complete for bipartite
graphs of maximum degree $k+1$ (and thus $L_{a}^{(k)}\leq k+1$). Hence,
4-Acyclic Colourability is NP-complete not only for graphs of maximum degree 5
[50], but also for bipartite graphs of maximum degree 5.

For each $k\geq 3$, we prove the following.

  1. 1.

$k$-Acyclic Colourability is NP-complete for bipartite graphs of maximum
degree $k+1$, and the problem does not admit a $2^{o(n)}$-time algorithm
unless ETH fails.

  2. 2.

$0.38\,k^{\,3/4}<L_{a}^{(k)}\leq k+1$.

  3. 3.

Provided $k\neq 3$, $k$-Acyclic Colourability is NP-complete for $d$-regular
graphs if and only if $L_{a}^{(k)}\leq d\leq 2k-3$.

  4. 4.

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).

##  2 Hardness Transitions of Acyclic Colouring

In this section, we discuss hardness transitions of acyclic colouring with
respect to the maximum degree. First, we show that (i) for $k\geq 3$,
$k$-Acyclic Colourability is NP-complete for graphs of maximum degree $k+1$,
and (ii) for $k\geq 4$ and $d\leq 2k-3$, $k$-Acyclic Colourability in graphs
of maximum degree $d$ is NP-complete if and only if $k$-Acyclic Colourability
in $d$-regular graphs is NP-complete. The consequences of these results on the
value of $L_{a}^{(k)}$ are discussed later in Section 2.1.

Let us start with a simple result due to Fertin et al. [25], which has direct
consequences for hardness transitions. We present a shorter proof, adapted
from [34], below.

######  Theorem 2 ([25]).

$\chi_{a}(G)>1+\frac{m}{n}$ for every non-empty graph $G$.

###### Proof $($adapted from [34] $)$..

Let $f\colon V(G)\to\\{0,1,\dots,k-1\\}$ be a $k$-acyclic colouring of $G$.
Recall that we denote the $i$th colour class $f^{-1}(i)$ by $V_{i}$ for $0\leq
i\leq k-1$. For every pair of colour classes $V_{i}$ and $V_{j}$, let $m_{ij}$
denote the number of edges from $V_{i}$ to $V_{j}$. Since $G[V_{i}\cup V_{j}]$
is a forest, we have $m_{ij}\leq|V_{i}|+|V_{j}|$, and equality holds only when
$|V_{i}|=|V_{j}|=0$. We know that some colour class is non-empty because $G$
is a non-empty graph. Summing up over all $i$ and $j$, we get $m<(k-1)n$ (for
instance, $|V_{0}|$ appears exactly $k-1$ times on the right side). Hence,
$k>1+(m/n)$. Since $f$ is an arbitrary $k$-acyclic colouring of $G$, we have
$\chi_{a}(G)>1+(m/n)$. ∎

Since $\frac{m}{n}=\frac{d}{2}$ for every $d$-regular graph $G$, we have the
following corollary.

######  Corollary 1.

$\chi_{a}(G)\geq\raisebox{1.0pt}{\big{\lceil}}\frac{d+3}{2}\raisebox{1.0pt}{\big{\rceil}}$
for every $d$-regular graph $G$ (provided $d\neq 0$). ∎

######  Corollary 2.

For every non-empty graph $G^{*}$,
$\chi_{a}(G^{*})>1+\frac{\textup{mad}(G^{*})}{2}$.

###### Proof.

Let $G$ be a subgraph of $G^{*}$ such that the average degree of $G$ is equal
to the maximum average degree of $G^{*}$. Applying Theorem 2 on $G$ proves the
corollary since $\chi_{a}(G^{*})\geq\chi_{a}(G)$ and
$|E(G)|/|V(G)|=\text{mad}(G^{*})/2$. ∎

Next, we show that the lower bound in Corollary 1 is attained by a vertex-
transitive $d$-regular graph for each $d$ (the graphs defined in the proof are
used later in a construction).

######  Theorem 3.

For all $d\geq 1$, there exists a $d$-regular vertex-transitive graph $G_{d}$
with
$\chi_{a}(G_{d})=\raisebox{1.0pt}{\big{\lceil}}\frac{d+3}{2}\raisebox{1.0pt}{\big{\rceil}}$.

###### Proof.

We first prove the theorem for every odd number $d$. To this end, we construct
a $(2p+1)$-regular graph $G_{2p+1}$ with acyclic chromatic number equal to
$p+2$ for all $p\geq 0$. The vertex set of $G_{2p+1}$ is $\\{(i,j)\colon
i,j\in\mathbb{Z},\ 0\leq i\leq p+1,\ 0\leq j\leq p+1,\ i\neq j\\}$, and
$(i,j)$ is adjacent to $(k,\ell)$ if $j=k$ or $i=\ell$ (or both). The graph
$G_{5}$ is shown in Figure 2. Note that $G_{2p+1}$ is a $(2p+1)$-regular
graph; for instance, the vertex $(0,1)$ in $G_{2p+1}$ has neighbours
$(1,2),\dots,(1,p+1),(1,0),(2,0),\dots,(p+1,0)$. Consider the function
$f\colon V(G_{2p+1})\to\\{0,1,\dots,p+1\\}$ defined as $f((i,j))=i$ for all
$(i,j)\in V(G_{2p+1})$. Let $V_{i}=f^{-1}(i)$ for $0\leq i\leq p+1$. It is
easy to verify that $f$ is a $(p+2)$-acyclic colouring of $G_{2p+1}$ (the
subgraph of $G$ induced by $V_{i}\cup V_{j}$ is two stars attached at
endvertices of the edge $\\{(i,j),(j,i)\\}$; observe that $u\in V_{i}$ is
adjacent to $v\in V_{j}$ if and only if $u=(i,j)$ or $v=(j,i)$). Thus,
$\chi_{a}(G_{2p+1})\leq p+2$. Thanks to Corollary 1, we have
$\chi_{a}(G_{2p+1})\geq\raisebox{1.0pt}{\big{\lceil}}\frac{(2p+1)+3}{2}\raisebox{1.0pt}{\big{\rceil}}=p+2$.
Hence, $\chi_{a}(G_{2p+1})=p+2$. Note that by the definition of the graph
$G_{2p+1}$, whether vertex $(i,j)$ is adjacent to vertex $(k,\ell)$ depends
only on equality and inequality between indices $i,j,k,\ell$. This ensures
that $G_{2p+1}$ is vertex-transitive. We include a short proof for
completeness. To construct an automorphism $\psi$ that maps a vertex $(i,j)$
to another vertex $(k,\ell)$, first choose a bijection $h$ from
$\\{0,1,\dots,p+1\\}$ to itself such that $h(i)=k$ and $h(j)=\ell$, and then
define $\psi\big{(}(x,y)\big{)}=\big{(}h(x),h(y)\big{)}$ for all $(x,y)\in
V(G_{2p+1})$.

$(0,1)$$(0,2)$$(0,3)$$(1,0)$$(1,2)$$(1,3)$$(2,0)$$(2,1)$$(2,3)$$(3,0)$$(3,1)$$(3,2)$
Figure 2: The graph $G_{5}$.
$(0,1)$$(0,2)$$(0,3)$$(1,0)$$(1,2)$$(1,3)$$(2,0)$$(2,1)$$(2,3)$$(3,0)$$(3,1)$$(3,2)$
Figure 3: The graph $G_{4}$ obtained from $G_{5}$ by deleting all
$\\{(i,j),(j,i)\\}$ edges.

Next, we prove the theorem for every even number $d$, by constructing a
$2p$-regular graph $G_{2p}$ with the acyclic chromatic number equal to $p+2$
for all $p\geq 1$. Observe that for all $p\geq 1$, the set $M$ of edges
between vertex pairs $(i,j)$ and $(j,i)$ in $G_{2p+1}$ is a perfect matching
of $G_{2p+1}$. We define $G_{2p}=G_{2p+1}-M$. The graph $G_{4}$ is shown in
Figure 3. Clearly, $G_{2p}$ is a $2p$-regular subgraph of $G_{2p+1}$, and thus
$\chi_{a}(G_{2p})\leq\chi_{a}(G_{2p+1})\leq p+2$. By Corollary 1,
$\chi_{a}(G_{2p})\geq\raisebox{1.0pt}{\big{\lceil}}\frac{2p+3}{2}\raisebox{1.0pt}{\big{\rceil}}=p+2$,
and thus $\chi_{a}(G_{2p})=p+2$. Moreover, the vertex set of $G_{2p}$ is
$\\{(i,j)\colon i,j\in\mathbb{Z},\ 0\leq i\leq p+1,\ 0\leq j\leq p+1,\ i\neq
j\\}$, and there is an edge joining $(i,j)$ to $(k,\ell)$ if either $j=k$ or
$i=\ell$ (not both). Thus, by its definition, $G_{2p}$ is vertex-transitive
(see [58, Theorem 4] for a detailed proof). ∎

_Remark:_ Note that $G_{1}\subseteq G_{3}\subseteq G_{5}\subseteq\dots$ and
$G_{2}\subseteq G_{4}\subseteq G_{6}\subseteq\dots$ by the definition of the
graphs $G_{d}$.

We are now ready to generalise the NP-completeness result of $3$-Acyclic
Colourability in bipartite graphs of maximum degree $4$ [54]: we show that for
each $k\geq 3$, $k$-Acyclic Colourability is NP-complete for bipartite graphs
of maximum degree $k+1$. The following simple observations are employed to
construct gadgets.

######  Observation 2.

Let $G$ be a graph, and let $f$ be a $q$-acyclic colouring of $G$, where
$q\leq k$. If two vertices $x$ and $y$ of $G$ have $k$ common neighbours, then
$f(x)\neq f(y)$.

###### Proof.

Let $x$ and $y$ be vertices in $G$ that share $k$ neighbours
$w_{1},w_{2},\dots,w_{k}$. Note that at least two among vertices
$w_{1},w_{2},\dots,w_{k}$ should get the same colour, say $f(w_{1})=f(w_{2})$
(if not, we need $k$ colours for vertices $w_{1},w_{2},\dots,w_{k}$, and thus
no colour is available for $x$). If $f(x)=f(y)$, then $(x,w_{1},y,w_{2})$ is a
bicoloured cycle; a contradiction. Hence, $f(x)\neq f(y)$. ∎

######  Observation 3.

Let $G(A\cup B,E)\cong K_{k-1,k}$ where $A$ and $B$ are independent sets in
$G$ with cardinality $k-1$ and $k$, respectively. Then, $\chi_{a}(G)=k$.
Moreover, for every $k$-acyclic colouring $f$ of $G$, (i) vertices in $A$
should get pairwise distinct colours, and (ii) all vertices in $B$ should get
the same colour $($i.e., $f(b)=f(b^{\prime})$ for all $b,b^{\prime}\in B)$.

###### Proof.

Let $f$ be a $q$-acyclic colouring of $G$, where $q=\chi_{a}(G)$. One can
obtain a $k$-acyclic colouring of $G$ by assigning a permutation of colours
$1,2,\dots,k-1$ on vertices in $A$ and colour 0 on vertices in $B$. Hence,
$q\leq k$. Every pair of vertices from $A$ have $k$ common neighbours. Hence,
vertices in $A$ should get pairwise distinct colours by Observation 2. That
is, $k-1$ distinct colours are used on vertices in $A$. Let $b\in B$. Since
all vertices in $A$ are adjacent to $b$, at least one more colour, say colour
$c_{1}$, is needed (to colour $b$). This proves that $q\geq k$, and thus
$\chi_{a}(G)=q=k$. Since $k-1$ distinct colours are used on vertices in $A$,
the remaining colour, namely colour $c_{1}$, is the only available colour for
each vertex in $B$. Thus, all vertices in $B$ should get colour $c_{1}$. ∎

Note that by Observation 3, the biclique $K_{k-1,k}$ has a unique $k$-acyclic
colouring up to colour swaps.

Level 1Level 2Level 3Level 4Level$2t-1$Level $2t$. .
.$\dots$$v^{\prime}_{1}$$\dots$$\dots$$v^{\prime}_{2}$$\dots$$\dots$$v^{\prime}_{t}$$\dots$$k-1$
(a)

Level 1Level 2Level 3Level 4Level$2t-1$Level $2t$. .
.12$k\\!-\\!1$$\dots$0000$v^{\prime}_{1}$$\dots$12$k\\!-\\!1$$\dots$0000$v^{\prime}_{2}$$\dots$12$k\\!-\\!1$$\dots$0000$v^{\prime}_{t}$$\dots$$k-1$
(b)

Figure 4: (a) The chain gadget, and (b) a $k$-acyclic colouring of the chain
gadget.

For every construction in this paper, only selected vertices within each
gadget are allowed to have neighbours outside the gadget. We call such
vertices as the _terminals_ of the gadget, and highlight them in diagrams by
drawing a circle around them.

The graph displayed in Figure 4(a), let us call it the chain gadget, plays a
major role in our constructions. In Figure 4(a), the terminals of the chain
gadget are labelled $v_{1}^{\prime},v_{2}^{\prime},\dots,v_{t}^{\prime}$,
where $t\in\mathbb{N}$. The next lemma explains the importance of the chain
gadget.

######  Lemma 1 (Properties of the chain gadget).

The colouring displayed in Figure 4(b) is the unique $k$-acyclic colouring of
the chain gadget up to colour swaps and automorphisms. In particular, the
following hold for every $k$-acyclic colouring of the chain gadget:
(i) there is a colour $c_{1}$ such that every terminal (of the chain gadget)
gets colour $c_{1}$, and
(ii) for every colour $c_{2}(\neq c_{1})$ and every pair of terminals $x$ and
$y$, there is an $x,y$-path coloured using only $c_{1}$ and $c_{2}$.

###### Proof.

Let $f$ be a $k$-acyclic colouring of the chain gadget. Observe that for each
$i\in\\{1,2,\dots,t\\}$, vertices of the chain gadget from Levels $2i-1$ and
$2i$ together form $K_{k-1,k}$. Therefore, for fixed $i$, vertices at Level
$2i-1$ get pairwise distinct colours, and vertices at Level $2i$ share the
same colour by Observation 3. Without loss of generality, assume that vertices
at Level 2 are coloured 0. Since each vertex at Level 3 has a neighbour in
Level 2, colour 0 is unavailable in Level 3. That means vertices in Level 3
are coloured $1,2,\dots,k-1$ in some order. Therefore, the colour shared by
vertices at Level 4 must be 0. Similarly, for all $i\in\\{1,2,\dots,t\\}$,
vertices at Level $2i$ are coloured 0 and vertices at Level $2i-1$ are
assigned a permutation of colours $1,2,\dots,k-1$. This proves that the
colouring displayed in Figure 4(b) is the unique $k$-acyclic colouring of the
chain gadget up to colour swaps and automorphisms (observe that applying a
permutation of colours on the set of vertices at Level $2j-1$ for each
$j\in\\{1,2,\dots,t\\}$ corresponds to an automorphism of the chain gadget;
see Section 4 in the supplementary material for a demonstration). Since all
terminals are coloured 0, Property (i) is proved. Observe that in Figure 4(b),
for every colour $c_{2}\neq 0$ and every pair of terminals $x$ and $y$, there
is an $x,y$-path coloured using only 0 and $c_{2}$ (for $x=v_{1}^{\prime}$,
$y=v_{t}^{\prime}$ and $c_{2}=1$, such an $x,y$-path is highlighted in Figure
4(b)). This proves Property (ii). ∎

The following construction is employed to prove NP-completeness of $k$-Acyclic
Colourability in bipartite graphs of maximum degree $k+1$.

###### Construction 2.

_Parameter:_ An integer $k\geq 3$.
_Input:_ A graph $G$ of maximum degree $2(k-1)$.
_Output:_ A bipartite graph $G^{\prime}$ of maximum degree $k+1$.
_Guarantee 1:_ $G$ is $k$-colourable if and only if $G^{\prime}$ is
$k$-acyclic colourable.
_Guarantee 2:_ $G^{\prime}$ has only $O(n)$ vertices where $n=|V(G)|$.
_Steps:_
Replace each vertex $v$ of $G$ by a chain gadget with $k\cdot\deg_{G}(v)$
terminals, and reserve $k$ terminals each for every neighbour of $v$ in $G$.
For each neighbour $u$ of $v$ in $G$, label the $k$ terminals of the chain
gadget for $v$ reserved for $u$ as $v_{u1},v_{u2},\dots,v_{uk}$. For each edge
$e=uv$ of $G$ and each $j\in\\{1,2,\dots,k\\}$, introduce a new vertex $e_{j}$
in $G^{\prime}$ and join $e_{j}$ to $u_{vj}$ as well as $v_{uj}$ (see Figure
5). An example of the construction is exhibited in Figure 6.

. . .. . .. . .. . .. . .. . .Level 1$\dots$Level
2$\dots$$\dots$$u_{v1}$$\dots$$\dots$$u_{v2}$$\dots$$\dots$$u_{vk}$$\dots$$\dots$Level$2k\cdot\deg_{G}(u)$$\dots$$k-1$(Chain
gadget for $u$)Level 1$\dots$Level
2$\dots$$\dots$$v_{u1}$$\dots$$\dots$$v_{u2}$$\dots$$\dots$$v_{uk}$$\dots$$\dots$Level$2k\cdot\deg_{G}(v)$$\dots$$k-1$(Chain
gadget for $v$)$e_{1}$$e_{2}$$e_{k}$$u$$v$$e$ Figure 5: Construction of
$G^{\prime}$ from $G$ (only vertices $u,v$ in $G$ and edge $uv$ in $G$, and
corresponding gadgets in $G^{\prime}$ are displayed).
$u$$v$$w$$x$$G$$e^{(1)}$$e^{(2)}$$e^{(3)}$$e^{(4)}$$u_{v1}$$u_{v2}$$u_{v3}$$u_{w1}$$u_{w2}$$u_{w3}$$u_{x1}$$u_{x2}$$u_{x3}$(gadget
for $u$)$v_{w1}$$v_{w2}$$v_{w3}$$v_{u1}$$v_{u2}$$v_{u3}$(gadget for
$v$)$w_{v1}$$w_{v2}$$w_{v3}$$w_{u1}$$w_{u2}$$w_{u3}$(gadget for
$w$)$x_{u1}$$x_{u2}$$x_{u3}$(gadget for
$x$)$e^{(1)}_{1}$$e^{(1)}_{2}$$e^{(1)}_{3}$$e^{(2)}_{1}$$e^{(2)}_{2}$$e^{(2)}_{3}$$e^{(4)}_{1}$$e^{(4)}_{2}$$e^{(4)}_{3}$$e^{(3)}_{1}$$e^{(3)}_{2}$$e^{(3)}_{3}$
Figure 6: Example of Construction 2 with $k=3$. Graph $G^{\prime}$ is
displayed large, and graph $G$ is shown inset (for convenience, a graph of
maximum degree 3 rather than 4 is used as $G$).

$G^{\prime}$ is clearly bipartite (small dots form one part and big dots form
the other part; see Figure 6).

###### Proof of Guarantee 1.

Suppose that $G$ admits a $k$-colouring $f:V(G)\to\\{0,1,\dots,k-1\\}$. We
produce a $k$-colouring $f^{\prime}$ of $G^{\prime}$ as follows, where
$f^{\prime}:V(G^{\prime})\to\\{0,1,\dots,k-1\\}$. For each vertex $v$ of $G$,
colour the chain gadget for $v$ by the scheme obtained from Figure 4(b) by
swapping colour 0 with $f(v)$. Now, the terminals of the chain gadget for $v$
have colour $f(v)$ under $f^{\prime}$. For each edge $e=uv$ of $G$, choose a
colour $c\in\\{0,1,\dots,k-1\\}\setminus\\{f(u),f(v)\\}$ and assign
$f^{\prime}(e_{j})=c$ for $1\leq j\leq k$. Since the paths of the form
$u_{vj},e_{j},v_{uj}$ are tricoloured by $f^{\prime}$, any cycle in
$G^{\prime}$ bicoloured by $f^{\prime}$ must be entirely within a chain
gadget. Since chain gadgets are coloured by an acyclic colouring scheme, they
do not contain any bicoloured cycle. Therefore, $f^{\prime}$ is a $k$-acyclic
colouring of $G^{\prime}$.

Conversely, suppose that $G^{\prime}$ admits a $k$-acyclic colouring
$f^{\prime}:V(G^{\prime})\to\\{0,1,\dots,k-1\\}$. By Property (i) of the chain
gadget (see Lemma 1), all terminals of a chain gadget get the same colour. For
brevity, let us call this colour as “the colour of the chain gadget”.

Claim 1: For every edge $uv$ of $G$, the colour of the chain gadget for $u$
differs from the colour of the chain gadget for $v$ (i.e.,
$f^{\prime}(u_{v1})\neq f^{\prime}(v_{u1})$ ).

Contrary to the claim, assume that $uv$ is an edge in $G$, but there is a
colour $c_{1}$ such that $f^{\prime}(u_{v1})=f^{\prime}(v_{u1})=c_{1}$.
Clearly, colour $c_{1}$ is unavailable for vertices $e_{j}$ ($1\leq j\leq k$).
Hence, by pigeon-hole principle, at least two vertices among
$e_{1},e_{2},\dots,e_{k}$ have the same colour, say $f(e_{p})=f(e_{q})=c_{2}$
where $p\neq q$ and $c_{2}\neq c_{1}$. By Property (ii) of the chain gadget
(see Lemma 1), the chain gadget for $u$ contains a path $R_{1}$ from $u_{vp}$
to $u_{vq}$ which is coloured using only $c_{1}$ and $c_{2}$. Similarly, the
chain gadget for $v$ contains a path $R_{2}$ from $v_{uq}$ to $v_{up}$ which
is coloured using only $c_{1}$ and $c_{2}$. These paths together with the
three-vertex paths $u_{vq},e_{q},v_{uq}$ and $v_{up},e_{p},u_{vp}$ form a
cycle in $G^{\prime}$ bicoloured by $f^{\prime}$ (namely, the cycle
$(u_{vp};R_{1};u_{vq},e_{q},v_{uq};R_{2};v_{up},e_{p})$ ). This contradiction
proves Claim 1.

Producing a $k$-colouring $f$ of $G$ from $f^{\prime}$ is easy. For each
vertex $v$ of $G$, assign at $v$, the colour of the chain gadget for $v$. The
function $f$ is a $k$-colouring of $G$ due to Claim 1. ∎

###### Proof of Guarantee 2.

Suppose that $G$ has $n$ vertices and $m$ edges. For each vertex $v$ of $G$,
the chain gadget for $v$ has $(2k-1)\cdot k\cdot\deg_{G}(v)$ vertices. Also,
there are only $km$ vertices outside of chain gadgets. Therefore, $G^{\prime}$
has $\left(\sum_{v\in
V(G)}(2k^{2}-k)\deg_{G}(v)\right)+km=\allowbreak(2k^{2}-k)\,2m+km=O(m)$
vertices. Since $m\leq n\Delta(G)/2$ and $\Delta(G)\leq 2(k-1)$, we have
$m=O(n)$, and thus the number of vertices in $G^{\prime}$ is $O(n)$. ∎

Since $G^{\prime}$ has only $O(n)$ vertices and the maximum degree of
$G^{\prime}$ is $k+1$, the graph $G^{\prime}$ has only $O(n)$ edges as well
($\because 2|E(G^{\prime})|=(k+1)|V(G^{\prime})|$ ). Hence, Construction 2
requires only time polynomial in the input size.

######  Theorem 4.

For $k\geq 3$, $k$-Acyclic Colourability$(\textup{bipartite, }\Delta=k+1)$ is
NP-complete, and the problem does not admit a $2^{o(n)}$-time algorithm unless
ETH fails.

###### Proof.

Fix an integer $k\geq 3$. We employ Construction 2 to establish a reduction
from $k$-Colourability$(\Delta=2(k-1))$ to $k$-Acyclic
Colourability$(\text{bipartite, }\Delta=k+1)$. The problem
$k$-Colourability$(\Delta=2(k-1))$ is NP-complete (in fact, $k$-Colourability
is NP-complete for line graphs of $k$-regular graphs [44]) and does not admit
a $2^{o(n)}$-time algorithm unless ETH fails (the latter can be observed from
a reduction of Emden-Weinert et al. [24]).

Let $G$ be an instance of $k$-Colourability$(\Delta=2(k-1))$. Produce a graph
$G^{\prime}$ from $G$ by Construction 2. Note that Construction 2 requires
only time polynomial in the size of $G$. By Guarantee 1 of Construction 2, $G$
is $k$-colourable if and only if $G^{\prime}$ is $k$-acyclic colourable.
Besides, the number of vertices in $G^{\prime}$ is $O(n)$ where $n=|V(G)|$.
Therefore, the problem $k$-Acyclic Colourability$(\text{bipartite,
}\Delta=k+1)$ is NP-complete, and it does not admit a $2^{o(n)}$-time
algorithm unless ETH fails. ∎

For $k\geq 3$, $k$-Acyclic Colourability is NP-complete for graphs of maximum
degree $k+1$ by Theorem 4. If $k$-Acyclic Colourability is NP-complete for
graphs of maximum degree $d$, then it is NP-complete for graphs of maximum
degree $d+1$. Thus, for $k\geq 3$ and $d\geq k+1$, $k$-Acyclic Colourability
in graphs of maximum degree $d$ is NP-complete. On the other hand, for all
$d\geq 2$ and every $d$-regular graph $G$, we have
$\chi_{a}(G)\geq\raisebox{1.0pt}{\big{\lceil}}\frac{d+3}{2}\raisebox{1.0pt}{\big{\rceil}}$,
and thus $G$ is not $k$-acyclic colourable for
$k<\raisebox{1.0pt}{\big{\lceil}}\frac{d+3}{2}\raisebox{1.0pt}{\big{\rceil}}$.
Hence, for $k\geq 3$ and $d\geq 2k-2$, $k$-Acyclic Colourability in
$d$-regular graphs is polynomial-time solvable (because
$k<\raisebox{1.0pt}{\big{\lceil}}\frac{(2k-2)+3}{2}\raisebox{1.0pt}{\big{\rceil}}\leq\raisebox{1.0pt}{\big{\lceil}}\frac{d+3}{2}\raisebox{1.0pt}{\big{\rceil}}$).
As a result, for $k\geq 3$ and $d\geq 2k-2$, $k$-Acyclic Colourability in
graphs of maximum degree $d$ is NP-complete (because $2k-2\geq k+1$) whereas
$k$-Acyclic Colourability in $d$-regular graphs is polynomial-time solvable.
In contrast, we use Construction 3 below to show that for all $k\geq 3$ and
$d\leq 2k-3$, the complexity of $k$-Acyclic Colourability is the same for
graphs of maximum degree $d$ and $d$-regular graphs. First, we construct a
gadget called the _filler gadget_ using the graph $G_{d}$. Note that for every
graph $H$ with an edge $xy$ and a $k$-acyclic colouring $h$, there is no
$x,y$-path in $H-xy$ bicoloured by $h$ (if not, that path together with the
edge $xy$ forms a cycle in $H$ bicoloured by $h$). In particular, the graph
$G_{d}$ defined in the proof of Theorem 3 is a $d$-regular graph with a
$k$-acyclic colouring $h$ (because
$\chi_{a}(G_{d})=\raisebox{1.0pt}{\big{\lceil}}\frac{d+3}{2}\raisebox{1.0pt}{\big{\rceil}}\leq\raisebox{1.0pt}{\big{\lceil}}\frac{(2k-3)+3}{2}\raisebox{1.0pt}{\big{\rceil}}=k$),
and for each edge $xy$ of $G_{d}$, there is no $x,y$-path in $G_{d}-xy$
bicoloured by $h$. We choose an edge $xy$ of $G_{d}$, and make the filler
gadget using $G_{d}-xy$ as shown in Figure 7. Note that every non-terminal
vertex of the filler gadget has degree $d$.

$x$$y$$G_{d}-xy$ Figure 7: The filler gadget in Construction 3 (except for
vertices $x$ and $y$, vertices and edges within the copy of $G_{d}-xy$ are not
displayed).

We use the vertex identification operation in Construction 3 (see Section 3 in
the supplementary material for the definition of vertex idenitification).

###### Construction 3.

_Parameters:_ Integers $k\geq 3$ and $d\leq 2k-3$.
_Input:_ A graph $G$ of maximum degree $d$.
_Output:_ A $d$-regular graph $G^{\prime}$.
_Guarantee:_ $G$ is $k$-acyclic colourable if and only if $G^{\prime}$ is
$k$-acyclic colourable.
_Steps:_
Introduce two copies of $G$, say $G^{(1)}$ and $G^{(2)}$. For each $v\in V(G)$
and $i\in\\{1,2\\}$, let $v^{(i)}$ denote the copy of $v$ in $G^{(i)}$. For
each $v\in V(G)$, introduce $d-\deg_{G}(v)$ filler gadgets, and for each of
these filler gadgets, identify its two terminals with $v^{(1)}$ and $v^{(2)}$,
respectively. See Figure 8 for an example.

$x=(2,0)$$y=(0,2)$$(0,1)$$(1,0)$$(1,2)$$(2,1)$ (a) $G_{3}-xy$

$v$$u$$w$$a$$b$ (b) $G$

$v^{(1)}$$u^{(1)}$$w^{(1)}$$a^{(1)}$$b^{(1)}$$v^{(2)}$$u^{(2)}$$w^{(2)}$$a^{(2)}$$b^{(2)}$
(c) $G^{\prime}$

Figure 8: Example of Construction 3 with $d=3$.

For every $v\in V(G)$ and $i\in\\{1,2\\}$, the vertex $v^{(i)}$ has (i)
$\deg_{G}(v)$ neighbours in $G^{(i)}$, and (ii) one neighbour in each of the
$d-\deg_{G}(v)$ filler gadgets attached at $v^{(i)}$; and thus $v^{(i)}$ has
degree $d$ in $G^{\prime}$. Recall that every non-terminal vertex of a filler
gadget has degree $d$ in $G^{\prime}$. Thus, $G^{\prime}$ is $d$-regular.

_Remark:_ In this construction, one can use any $k$-acyclic colourable
$d$-regular graph in place of $G_{d}$ to construct a filler gadget. We chose a
fixed graph, namely $G_{d}$, for definiteness.

###### Proof of Guarantee.

If $G^{\prime}$ is $k$-acyclic colourable, then its subgraph $G$ is
$k$-acyclic colourable. Conversely, suppose that $G$ admits a $k$-acyclic
colouring $f$. We produce a $k$-colouring $f^{\prime}$ of $G^{\prime}$ as
follows. First, colour both copies of $G$ using $f$. Next, we colour the
filler gadgets. For every $v\in V(G)$, (i) choose two distinct colours
$c_{1},c_{2}\in\\{0,1,\dots,k-1\\}\setminus\\{f(v)\\}$ and a $k$-acyclic
colouring $h$ of $G_{d}-xy$ such that $h(x)=c_{1}$ and $h(y)=c_{2}$, and (ii)
use $h$ to complete the colouring of the filler gadgets with terminals
$v^{(1)}$ and $v^{(2)}$. If a filler gadget contains a path $Q$ between its
terminals $v^{(1)}$ and $v^{(2)}$, then $f^{\prime}$ uses at least three
colours (namely, $c_{1},c_{2}$ and $f(v)$) on $Q$, and thus $Q$ is not
bicoloured by $f^{\prime}$. Therefore, paths such as $Q$ cannot be part of any
cycle in $G^{\prime}$ bicoloured by $f^{\prime}$. This ensures that
$f^{\prime}$ is a $k$-acyclic colouring of $G^{\prime}$ since $f^{\prime}$
colours the copies of $G$ and the copies of $G_{d}-xy$ in $G^{\prime}$ using
acyclic colouring schemes. ∎

The graph $G^{\prime}$ contains two copies of $G$ and at most $dn$ copies of
the filler gadget. Since $G_{d}$ is a fixed graph, $G^{\prime}$ has at most
$2n+dn\cdot O(1)=O(n)$ vertices and $2m+\mbox{$dn\cdot O(1)$}=O(m+n)$ edges,
where $m=|E(G)|$ and $n=|V(G)|$. Thus, Construction 3 requires only time
polynomial in $m+n$.

Due to Theorem 4, for all $k\geq 3$ and $d\geq k+1$, $k$-Acyclic Colourability
is NP-complete for graphs of maximum degree $d$. For $k\geq 3$ and $d\leq
2k-3$, Construction 3 establishes a reduction from $k$-Acyclic
Colourability($\Delta=d$) to $k$-Acyclic Colourability($d$-regular). Hence,
for $k\geq 3$ and $d\leq 2k-3$, if $k$-Acyclic Colourability is NP-complete
for graphs of maximum degree $d$, then $k$-Acyclic Colourability is NP-
complete for $d$-regular graphs. Clearly, if $k$-Acyclic Colourability is NP-
complete for $d$-regular graphs, then $k$-Acyclic Colourability is NP-complete
for graphs of maximum degree $d$. Thus, we have the following theorem.

######  Theorem 5.

For all $k\geq 3$ and $d\leq 2k-3$, $k$-Acyclic Colourability is NP-complete
for graphs of maximum degree $d$ if and only if $k$-Acyclic Colourability is
NP-complete for $d$-regular graphs. In particular, for $k\geq 4$ and $k+1\leq
d\leq 2k-3$, $k$-Acyclic Colourability is NP-complete for $d$-regular graphs.
∎

A modification of Construction 3 gives the following theorem.

######  Theorem 6.

For all $k\geq 3$ and $d\leq 2k-3$, $k$-Acyclic Colourability is NP-complete
for bipartite graphs of maximum degree $d$ if and only if $k$-Acyclic
Colourability is NP-complete for $d$-regular bipartite graphs. In particular,
for $k\geq 4$ and $k+1\leq d\leq 2k-3$, $k$-Acyclic Colourability is NP-
complete for $d$-regular bipartite graphs.

###### Proof.

First, we prove that for $k\geq 3$ and $d\leq 2k-3$, if $k$-Acyclic
Colourability is NP-complete for bipartite graphs of maximum degree $d$, then
$k$-Acyclic Colourability is NP-complete for $d$-regular bipartite graphs. As
remarked earlier, any $k$-acyclic colourable $d$-regular graph $H$ can replace
the graph $G_{d}$ in Construction 3 without affecting the guarantee in the
construction. Hence, it is enough to prove the following claim to complete the
proof.
Claim: $G^{\prime}$ is bipartite if $G$ and $H$ are bipartite.
To prove the claim, assume that $G$ and $H$ are bipartite. Let $f$ be a
2-colouring of $G$ and $h$ be a 2-colouring of $H$. Since $xy$ is an edge in
$H$, we have $h(x)\neq h(y)$. Without loss of generality, assume that $h(x)=0$
and $h(y)=1$. It suffices to produce a 2-colouring $f^{\prime}$ of
$G^{\prime}$. For each $v\in V(G)$, assign $f^{\prime}(v^{(1)})=f(v)$ and
$f^{\prime}(v^{(2)})=1-f(v)$.

$x$0$y$1$H-xy$$v^{(1)}$1$v^{(2)}$0 (a) When $f(v)=1$

$x$1$y$0$H-xy$$v^{(1)}$0$v^{(2)}$1 (b) When $f(v)=0$

Figure 9: 2-colouring schemes for filler gadget when $H$ is bipartite. For
each vertex $z$ in $H-xy$, scheme (a) assigns colour $h(z)$ whereas scheme (b)
assigns colour $1-h(z)$.

Next, for each $v\in V(G)$, we colour the filler gadgets with terminals
$v^{(1)}$ and $v^{(2)}$. If $f^{\prime}(v^{(1)})=1$, colour the filler gadget
by the scheme in Figure 9(a); otherwise, use the scheme in Figure 9(b). It is
easy to verify that $f^{\prime}$ is indeed a 2-colouring of $G^{\prime}$.

We know that for $k\geq 4$ and $d\geq k+1$, $k$-Acyclic Colourability is NP-
complete for bipartite graphs of maximum degree $d$. As a result, for $k\geq
4$ and $k+1\leq d\leq 2k-3$, $k$-Acyclic Colourability is NP-complete for
$d$-regular bipartite graphs. ∎

###  2.1 Results on $L_{a}^{(k)}$

Recall that for $k\geq 3$, $L_{a}^{(k)}$ is the least integer $d$ such that
$k$-Acyclic Colourability in graphs of maximum degree $d$ is NP-complete. Bear
in mind that we assume P $\neq$ NP throughout this paper; thus, NP is
partitioned into three classes: P, NPC and NPI [55]. If a problem in NP is not
NP-complete (i.e., not in NPC), then it is either in P or in NPI. By the
definition of $L_{a}^{(k)}$, $k$-Acyclic Colourability($\Delta=d$) is not NP-
complete for $d<L_{a}^{(k)}$, which means that the problem is either in P or
in NPI (we do not know which is the case).

Theorem 4 proved that for $k\geq 3$, $k$-Acyclic Colourability is NP-complete
for graphs of maximum degree $k+1$, and thus $L_{a}^{(k)}\leq k+1$. It is easy
to observe that for $d\leq 2$, the acyclic chromatic number of a graph of
maximum degree $d$ can be computed in polynomial time. Hence, $L_{a}^{(k)}\geq
3$ for all $k\geq 3$. Next, we show that $0.38\,k^{\,3/4}<L_{a}^{(k)}\leq k+1$
for all $k\geq 3$.

######  Observation 4.

For $d\leq 0.38\,k^{\,3/4}$, $k$-Acyclic Colourability is polynomial-time
solvable for graphs of maximum degree $d$. Hence,
$L_{a}^{(k)}>0.38\,k^{\,3/4}$ for all $k\geq 3$.

###### Proof.

The observation is trivially true for $d\leq 2$. It suffices to prove the
observation for $d\geq 3$. Suppose that $d\geq 3$. Sereni and Volec [57]
proved that $\chi_{a}(G)<2.835\,d^{\,4/3}+d$ for every graph $G$ of maximum
degree $d$. Since $d\geq 3$, we have $d^{\,1/3}\geq 3^{1/3}>1/0.694$, and thus
$d<0.694\,d^{\,4/3}$. Thus,
$\chi_{a}(G)<(2.835+0.694)d^{\,4/3}=3.529\,d^{\,4/3}$ for every graph $G$ of
maximum degree $d$. Hence, when $k\geq 3.529\,d^{\,4/3}$, every graph of
maximum degree $d$ is $k$-acyclic colourable. In other words, if
$d\leq(3.529)^{-3/4}k^{\,3/4}$, then every graph of maximum degree $d$ is
$k$-acyclic colourable. Note that $0.38<(3.529)^{-3/4}$. Hence, if $d\leq
0.38k^{3/4}$, then $d\leq(3.529)^{-3/4}k^{3/4}$. Therefore, for $d\leq
0.38\,k^{3/4}$, every graph of maximum degree $d$ is $k$-acyclic colourable,
and thus $k$-Acyclic Colourability is polynomial-time solvable for graphs of
maximum degree $d$. As a result, $L_{a}^{(k)}>0.38\,k^{3/4}$ for all $k\geq
3$. ∎

By Corollary 1, $\chi_{a}(G)\geq\lceil(d+3)/2\rceil$ for every $d$-regular
graph $G$. Hence, for $k\geq 3$, $k$-Acyclic Colourability in $d$-regular
graphs is polynomial-time solvable for each $d\geq 2k-2$ (because the answer
is always ‘no’).

Fix an integer $k\geq 4$. Theorem 6 proved that for $d\leq 2k-3$, $k$-Acyclic
Colourability in graphs of maximum degree $d$ is NP-complete if and only if
$k$-Acyclic Colourability in $d$-regular graphs is NP-complete. By the
definition of $L_{a}^{(k)}$, $k$-Acyclic Colourability in graphs of maximum
degree $d$ is NP-complete for $d=L_{a}^{(k)}$, and not NP-complete for
$d<L_{a}^{(k)}$. Hence, for $d<L_{a}^{(k)}$, $k$-Acyclic Colourability in
$d$-regular graphs is not NP-complete by Theorem 6. We know that $k$-Acyclic
Colourability in graphs of maximum degree $d$ is NP-complete for $d\geq
L_{a}^{(k)}$. As a result, for $d$ in the range $L_{a}^{(k)}\leq d\leq 2k-3$,
$k$-Acyclic Colourability in $d$-regular graphs is also NP-complete by Theorem
6. Moreover, for $d\geq 2k-2$, $k$-Acyclic Colourability in $d$-regular graphs
is polynomial-time solvable (see the previous paragraph). Thus, we have the
following theorem.

######  Theorem 7.

For $k\geq 4$, $k$-Acyclic Colourability in $d$-regular graphs is NP-complete
if and only if $L_{a}^{(k)}\leq d\leq 2k-3$. ∎

##  3 Unique Acyclic Colouring

In this section, we borrow gadgets from Construction 2 to obtain results on
unique acyclic colouring. See Section 1.4 for definitions of problems related
to unique colouring and unique acyclic colouring. We prove that for all $k\geq
3$, Another $k$-Acyclic Colouring [$\mathcal{R}_{\text{swap}}$] and Another
$k$-Acyclic Colouring [$\mathcal{R}_{\text{swap+auto}}$] are NP-complete and
thus the corresponding unique solution problems are coNP-hard. We also show
that Unique 3-Acyclic Colouring [$\mathcal{R}_{\text{swap+auto}}$] is coNP-
hard for the class of bipartite graphs of maximum degree 4.

We start with a simple construction that enables us to transform Unique
3-Colouring [$\mathcal{R}_{\text{swap}}$] to Unique 3-Acyclic Colouring
[$\mathcal{R}_{\text{swap}}$]. Observation 3 proved that the biclique
$K_{k-1,k}$ has a unique $k$-acyclic colouring up to colour swaps. In
particular, $K_{2,3}$ has a unique 3-acyclic colouring up to colour swaps. The
following construction makes use of this.

###### Construction 4.

_Input:_ A graph $G$ of maximum degree 8.
_Output:_ A 2-degenerate bipartite graph $G^{\prime}$ of maximum degree 24.
_Guarantee:_ The number of $3$-colourings of $G$ up to colour swaps equals the
number of $3$-acyclic colourings of $G^{\prime}$ up to colour swaps.
_Steps:_
Replace each edge $e=uv$ of $G$ by a copy of the complete bipartite graph
$K_{2,3}$ with parts $\\{u,v\\}$ and $\\{e_{1},e_{2},e_{3}\\}$ where
$e_{1},e_{2}$ and $e_{3}$ are newly introduced vertices. To produce a
2-degenerate ordering of $V(G^{\prime})$, list the new vertices $e_{i}$
followed by the members of $V(G)$.

###### Proof of Guarantee.

For each 3-colouring $f$ of $G$ that uses colours 0,1 and 2, there exists a
unique 3-colouring extension of $f$ into $V(G^{\prime})$. The extension is
unique because for each edge $e=uv$ of $G$, exactly one colour, namely the
unique colour in $\\{0,1,2\\}\setminus\\{f(u),f(v)\\}$, is available for
$e_{1},e_{2}$ and $e_{3}$. Let $\phi$ be the function that maps each
3-colouring of $G$ to its unique 3-colouring extension into $V(G^{\prime})$.
Clearly, $\phi$ is a function from the set of 3-colourings of $G$ to the set
of 3-colourings of $G^{\prime}$, and $\phi$ is one-one.

We claim that $\text{Range}(\phi)$ is precisely the set of 3-acyclic
colourings of $G^{\prime}$. For every 3-colouring $f$ of $G$, we know that
$\phi(f)$ is a 3-acyclic colouring of $G^{\prime}$ because every cycle in
$G^{\prime}$ contains a path of the form $u,e_{i},v$ where $u,v\in V(G)$ and
$uv\in E(G)$, and such paths are tricoloured by $\phi(f)$ since
$\phi(f)(u)=f(u)\neq f(v)=\phi(f)(v)$. Moreover, each 3-acyclic colouring of
the complete bipartite graph $K_{2,3}$ with parts $\\{u,v\\}$ and
$\\{e_{1},e_{2},e_{3}\\}$ assigns different colours to $u$ and $v$ by the
special case $k=3$ of Observation 2. Thus, every 3-acyclic colouring
$f^{\prime}$ of $G^{\prime}$ has a preimage under $\phi$, namely the
restriction of $f^{\prime}$ to $V(G)$. This proves that $\phi$ is onto. Thus,
there exists a one-one function $\phi$ from the set of 3-colourings of $G$
onto the set of 3-acyclic colourings of $G^{\prime}$. Furthermore, two
3-colourings $f_{1}$ and $f_{2}$ of $G$ are non-equivalent under colour swaps
if and only if the 3-acyclic colourings $\phi(f_{1})$ and $\phi(f_{2})$ of
$G^{\prime}$ are non-equivalent under colour swaps. ∎

######  Theorem 8.

For 2-degenerate bipartite graphs of maximum degree 24, Another 3-Acyclic
Colouring $[\mathcal{R}_{\text{swap}}]$ is NP-complete and Unique 3-Acyclic
Colouring $[\mathcal{R}_{\text{swap}}]$ is coNP-hard.

###### Proof.

The reduction is from Another 3-Colouring [$\mathcal{R}_{\text{swap}}$]
($\Delta=8$). Let $(G,f)$ be an instance of the source problem. From $G$,
produce a graph $G^{\prime}$ by Construction 4. In Construction 4, it is
established that there is a bijection $\phi$ from the set of 3-colourings of
$G$ to the set of 3-acyclic colourings of $G^{\prime}$. In particular,
$f^{\prime}=\phi(f)$ is a 3-acyclic colouring of $G^{\prime}$. By the
guarantee in Construction 4, the number of 3-colourings of $G$ up to colour
swaps is equal to the number of 3-acyclic colourings of $G^{\prime}$ up to
colour swaps. Therefore, $(G,f)$ is a yes instance of Another 3-Colouring
[$\mathcal{R}_{\text{swap}}$] if and only if $(G^{\prime},f^{\prime})$ is a
yes instance of Another 3-Acyclic Colouring [$\mathcal{R}_{\text{swap}}$].
This proves that Another 3-Acyclic Colouring [$\mathcal{R}_{\text{swap}}$] is
NP-complete for 2-degenerate bipartite graphs of maximum degree 24, and thus
the problem Unique 3-Acyclic Colouring [$\mathcal{R}_{\text{swap}}$] is coNP-
hard for the same class. ∎

Next, we show that Another $k$-Acyclic Colouring [$\mathcal{R}_{\text{swap}}$]
is NP-complete and Unique $k$-Acyclic Colouring [$\mathcal{R}_{\text{swap}}$]
in coNP-hard for all $k\geq 3$. Let $G$ be a graph, and let $G^{\prime}$ be
the graph obtained by adding a universal vertex to $G$; that is, $G^{\prime}$
is the graph join of $G$ and $K_{1}$. Fix an integer $k\geq 3$. Clearly, $G$
is $k$-acyclic colourable if and only if $G^{\prime}$ is $(k+1)$-acyclic
colourable. Moreover, $G$ admits two $k$-acyclic colourings $f_{1}$ and
$f_{2}$ non-equivalent up to colour swaps (i.e.,
$(f_{1},f_{2})\notin\mathcal{R}_{\text{swap}}(G,k)$) if and only if
$G^{\prime}$ admits two $(k+1)$-acyclic colourings $f_{1}^{\prime}$ and
$f_{2}^{\prime}$ non-equivalent up to colour swaps (i.e.,
$(f_{1}^{\prime},f_{2}^{\prime})\notin\mathcal{R}_{\text{swap}}(G^{\prime},k+1)$).
Thus, $G$ admits a unique $k$-acyclic colouring up to colour swaps if and only
if $G^{\prime}$ admits a unique $(k+1)$-acyclic colouring up to colour swaps.
Hence, for $k\geq 3$, the transformation from $(G,k)$ to $(G^{\prime},k+1)$
establishes a reduction from Another $k$-Acyclic Colouring
[$\mathcal{R}_{\text{swap}}$] to Another $(k+1)$-Acyclic Colouring
[$\mathcal{R}_{\text{swap}}$]. Thus, we have the following theorem by Theorem
8 and induction.

######  Theorem 9.

For $k\geq 3$, Another $k$-Acyclic Colouring $[\mathcal{R}_{\text{swap}}]$ is
NP-complete and Unique $k$-Acyclic Colouring $[\mathcal{R}_{\text{swap}}]$ is
coNP-hard. ∎

Finally, we prove that Another $k$-Acyclic Colouring
[$\mathcal{R}_{\text{swap+auto}}$] is NP-complete for all $k\geq 3$. We prove
this for $k=3$ first by Construction 5 below, which establishes a reduction
from Another 3-Colouring [$\mathcal{R}_{\text{swap}}$] ($\Delta=8$) to the
problem Another 3-Acyclic Colouring [$\mathcal{R}_{\text{swap+auto}}$]
($\Delta=4$). Construction 5 is a slight modification of Construction 2.

###### Construction 5.

_Input:_ A graph $G$ of maximum degree 8.
_Output:_ A bipartite graph $G^{*}$ of maximum degree 4.
_Guarantee:_ $G$ has a unique 3-colouring up to colour swaps if and only if
$G^{*}$ has a unique 3-acyclic colouring up to colour swaps and automorphisms.
_Steps:_
Replace each vertex $v$ of $G$ by a chain gadget with
$3\deg_{G}(v)+\lambda(v)$ terminals, where $\lambda\colon V(G)\to\mathbb{N}$
is defined in such a way that no two chain gadgets have the same number of
terminals (one way to ensure this is to choose an ordering
$v_{1},v_{2},\dots,v_{n}$ of the vertex set of $G$ such that
$\deg_{G}(v_{1})\leq\deg_{G}(v_{2})\leq\dots\leq\deg_{G}(v_{n})$, and define
$\lambda(v_{i})=i$ for $1\leq i\leq n$). For each $v\in V(G)$ and each
neighbour $u$ of $v$, the chain gadget for $v$ (let us call it
$\text{chain}(v)$) has three terminals reserved for $u$, which we shall call
as $v_{u1}$, $v_{u2}$ and $v_{u3}$. For each edge $e=uv$ of $G$ and each
$j\in\\{1,2,3\\}$, introduce a new vertex $e_{j}$ in $G^{*}$ and join $e_{j}$
to $u_{vj}$ as well as $v_{uj}$. An example of the construction is shown in
Figure 10.

$u$$v$$w$$x$$G$$e^{(1)}$$e^{(2)}$$e^{(3)}$$e^{(4)}$$u_{v1}$$u_{v2}$$u_{v3}$$u_{w1}$$u_{w2}$$u_{w3}$$u_{x1}$$u_{x2}$$u_{x3}$(gadget
for $u$)$v_{w1}$$v_{w2}$$v_{w3}$$v_{u1}$$v_{u2}$$v_{u3}$(gadget for
$v$)$w_{v1}$$w_{v2}$$w_{v3}$$w_{u1}$$w_{u2}$$w_{u3}$(gadget for
$w$)$x_{u1}$$x_{u2}$$x_{u3}$(gadget for
$x$)$e^{(1)}_{1}$$e^{(1)}_{2}$$e^{(1)}_{3}$$e^{(2)}_{1}$$e^{(2)}_{2}$$e^{(2)}_{3}$$e^{(4)}_{1}$$e^{(4)}_{2}$$e^{(4)}_{3}$$e^{(3)}_{1}$$e^{(3)}_{2}$$e^{(3)}_{3}$
Figure 10: Example of Construction 5 with $k=3$ (here, $\lambda(u)=3$,
$\lambda(v)=1$, $\lambda(w)=4$ and $\lambda(x)=2$). Graph $G^{*}$ is displayed
large, and graph $G$ is shown inset (for convenience, a graph of maximum
degree 3 rather than 8 is used as $G$).

###### Proof of Guarantee.

First, we construct a surjective mapping $\phi$ from the set of 3-acyclic
colourings of $G^{*}$ to the set of 3-colourings of $G$. Then, we show that
$\phi$ gives a bijection from the set of 3-acyclic colourings of $G^{*}$ up to
automorphisms to the set of 3-colourings of $G$. This proves that $\phi$ is a
bijection from the set of 3-acyclic colourings of $G^{*}$ up to colour swaps
and automorphisms to the set of 3-colourings of $G$ up to colour swaps (that
is, if $\mathcal{R}^{*}$ is the equivalence relation
$\mathcal{R}_{\text{swap+auto}}(G^{*},3)$ restricted to the set of 3-acyclic
colourings of $G^{*}$, then $\phi$ is a bijection from the set of equivalence
classes of $\mathcal{R}^{*}$ to the set of equivalence classes of
$\mathcal{R}_{\text{swap}}(G,3)$). Before constructing $\phi$, we discuss the
structure of automorphisms of $G^{*}$.

Let $\text{Aut}(G^{*},v)$ denote the set of automorphisms $\psi$ of $G^{*}$
such that $\psi$ fixes all vertices not in $\text{chain}(v)$; i.e.,
$\psi(x)=x$ for all $x\in V(G^{*})\setminus V(\text{chain}(v))$. Since no two
chain gadgets have the same number of terminals, each automorphism of $G^{*}$
is in a sense composed of automorphisms of the chain gadgets. This is formally
expressed as Claim 1 below (see Section 5 in the supplementary material for
proof).

###### Claim 1:

For every automorphism $\psi$ of $G^{*}$, there exists an automorphism
$\psi_{v}$ for each $v\in V(G)$ such that $\psi$ equals the function
composition of $\psi_{v}$’s
(i.e., if $V(G)=\\{v_{1},v_{2},\dots,v_{n}\\}$, then for every automorphism
$\psi$ of $G^{*}$, there exist
$\psi_{1}\in\text{Aut}(G^{*},v_{1})$, …, $\psi_{n}\in\text{Aut}(G^{*},v_{n})$
such that $\psi=\psi_{1}\circ\psi_{2}\circ\dots\circ\psi_{n}$).

Moreover, we have the following claim (for a proof, see Claim 1.6 in Section 5
of the supplementary material).

###### Claim 2:

For each vertex $v$ of $G$, each automorphism $\psi$ of $G^{*}$ maps each
vertex in Level $j$ of $\text{chain}(v)$ to some vertex in Level $j$ of
$\text{chain}(v)$, where $j\in\mathbb{N}$.

Note that the chain gadget used here is the special case $k=3$ of the chain
gadget in Lemma 1. By Lemma 1, this chain gadget has exactly one 3-acyclic
colouring up to colour swaps and automorphisms. In particular, the terminals
of a chain gadget get the same colour under a 3-acyclic colouring (and we
shall call this colour as the _colour of the chain gadget_). Note that if $G$
is given as input, the output graph $G^{\prime}$ in Construction 2 with $k=3$
is a subgraph of $G^{*}$ (compare Figure 6 with Figure 10). Hence, as in
Construction 2, for each edge $uv$ of $G$, the colour of $\text{chain}(u)$
differs from the colour of $\text{chain}(v)$ under each 3-acyclic colouring
$f^{*}$ of $G^{*}$. Hence, for every 3-acyclic colouring $f^{*}$ of $G^{*}$,
there exists a corresponding 3-colouring $f$ of $G$ such that $f(v)$ equals
the colour of $\text{chain}(v)$ for each $v\in V(G)$.

Let $\phi$ be the function that maps each 3-acyclic colouring $f^{*}$ of
$G^{*}$ to this corresponding 3-colouring $f$ of $G$. The next claim shows
that $\phi$ is onto.

###### Claim 3:

Every 3-colouring $f$ of $G$ has a preimage under $\phi$.

Let $f$ be a 3-colouring of $G$. We claim that the colouring $f^{*}$ of
$G^{*}$ defined as follows is a preimage of $f$ under $\phi$: for each vertex
$v$ of $G$, colour the chain gadget for vertex $v$ by assigning the colour
$f(v)$ on vertices of Level $2j$ and the remaining two colours on vertices of
Level $2j-1$ for each $j$; whenever $e=uv$ is an edge in $G$, colour the
vertices $e_{1},e_{2}$ and $e_{3}$ by the only colour different from both
$f(u)$ and $f(v)$. Since the paths of the form $u_{v\,j},e_{j},v_{u\,j}$ are
tricoloured, any bicoloured cycle in $G^{*}$ must be entirely within a chain
gadget. But, an acyclic colouring scheme is used on each chain gadget.
Therefore, there is no cycle in $G^{*}$ bicoloured by $f^{*}$. This proves
Claim 3.

###### Claim 4:

If two 3-acyclic colourings $f_{1}^{*}$ and $f_{2}^{*}$ of $G^{*}$ are the
same up to automorphisms, then $\phi(f_{1}^{*})=\phi(f_{2}^{*})$.

Let $f_{1}^{*}$ and $f_{2}^{*}$ be 3-acyclic colourings of $G^{*}$ which are
the same up to automorphisms. That is, there exists an automorphism $\psi$ of
$G^{*}$ such that $f_{1}^{*}(\psi(x))=f_{2}^{*}(x)$ for all $x\in V(G^{*})$.
By the special case $k=3$ of Lemma 1, the chain gadget has exactly one
3-acyclic colouring up to colour swaps and automorphisms, namely the colouring
in Figure 4(b). Observe that all even-level vertices have the same colour in
Figure 4(b). Also, observe that every automorphism of the chain gadget maps
vertices on Level $j$ to vertices on Level $j$ for each $j\in\mathbb{N}$ (for
a proof, see Claim 1.5 in Section 5 of the supplementary material). Hence, for
every 3-acyclic colouring of the chain gadget, there is a colour $c$ such that
all even-level vertices of the chain gadget are coloured $c$. In particular,
for each $v\in V(G)$ and each $i\in\\{1,2\\}$, there is a colour $c_{v}^{(i)}$
such that $f_{i}^{*}$ assigns colour $c_{v}^{(i)}$ on all even-level vertices
of $\text{chain}(v)$. Consider an arbitrary vertex $v$ of $G$ and an arbitrary
vertex $x_{v}$ at Level $2j$ of $\text{chain}(v)$ for some $j\in\mathbb{N}$.
We know that $f_{i}^{*}$ assigns colour $c_{v}^{(i)}$ on even-level vertices
of $\text{chain}(v)$ for $i\in\\{1,2\\}$. In particular,
$f_{1}^{*}(x_{v})=c_{v}^{(1)}$. Since $\psi$ maps $x_{v}$ to a vertex in Level
$2j$ of $\text{chain}(v)$, $f_{2}^{*}(\psi(x_{v}))=c_{v}^{(2)}$. Since
$f_{2}^{*}(\psi(x))=f_{1}^{*}(x)$ for all $x\in V(G^{*})$, we have
$c_{v}^{(1)}=f_{1}^{*}(x_{v})=f_{2}^{*}(\psi(x_{v}))=c_{v}^{(2)}$. For
$i\in\\{1,2\\}$, $f_{i}^{*}$ assigns colour $c_{v}^{(i)}$ on even-level
vertices of $\text{chain}(v)$ and in particular terminals of
$\text{chain}(v)$. Thus, $c_{v}^{(i)}$ is the colour of $\text{chain}(v)$
under $f_{i}^{*}$ for $i\in\\{1,2\\}$. Hence,
$(\phi(f_{i}^{*}))(v)=c_{v}^{(i)}$ for $i\in\\{1,2\\}$. Since
$c_{v}^{(1)}=c_{v}^{(2)}$ , we have
$(\phi(f_{1}^{*}))(v)=(\phi(f_{2}^{*}))(v)$. Since $v$ is arbitrary,
$\phi(f_{1}^{*})=\phi(f_{2}^{*})$. This proves Claim 4.

###### Claim 5:

If $\phi(f_{1}^{*})=\phi(f_{2}^{*})$ for two 3-acyclic colourings $f_{1}^{*}$
and $f_{2}^{*}$ of $G^{*}$, then $f_{1}^{*}$ and $f_{2}^{*}$ are the same up
to automorphisms.

Let $f_{1}^{*}$ and $f_{2}^{*}$ be two 3-acyclic colourings of $G^{*}$, and
let $\phi(f_{1}^{*})=\phi(f_{2}^{*})$. Consider an arbitrary vertex $v$ of
$G$. Suppose that $\text{chain}(v)$ has $\ell$ terminals. Since
$\phi(f_{1}^{*})=\phi(f_{2}^{*})$, the colour of $\text{chain}(v)$ under
$f_{1}^{*}$ is equal to the colour of $\text{chain}(v)$ under $f_{2}^{*}$. By
the special case $k=3$ of Lemma 1, the chain gadget has exactly one 3-acyclic
colouring up to colour swaps and automorphisms, namely the colouring in Figure
4(b). Observe that in Figure 4(b), (i) all even-level vertices have colour 0,
and (ii) for $k=3$, for each $j\in\\{1,2,\dots,\ell\\}$, vertices at Level
$2j-1$ are assigned colours 1 and 2 from left to right. Also, observe that
every automorphism of the chain gadget maps vertices on Level $j$ to vertices
on Level $j$ for each $j\in\mathbb{N}$ (for a proof, see Claim 1.5 in Section
5 of the supplementary material). Hence, for every 3-acyclic colouring of
$\text{chain}(v)$, there is a colour $c$ such that (i) all even-level vertices
(of $\text{chain}(v)$) are coloured $c$, and (ii) for each
$j\in\\{1,2,\dots,\ell\\}$, vertices at Level $2j-1$ are assigned colours 1
and 2 in some order. Thus, for $i\in\\{1,2\\}$, $f_{i}^{*}$ assigns the same
colour, say colour $c_{i}$, on even-level vertices of $\text{chain}(v)$ and in
particular on the terminals of $\text{chain}(v)$. Since the colour on
terminals of $\text{chain}(v)$ under $f_{1}^{*}$ (i.e., the colour of
$\text{chain}(v)$ under $f_{1}^{*}$) is equal to the colour on terminals of
$\text{chain}(v)$ under $f_{2}^{*}$, we have $c_{1}=c_{2}$. That is, both
$f_{1}^{*}$ and $f_{2}^{*}$ assign the same colour, say colour $c$, on even-
level vertices of $\text{chain}(v)$. Owing to this and the fact that both
$f_{1}^{*}$ and $f_{2}^{*}$ assign a permutation of colours
$\\{0,1,2\\}\setminus\\{c\\}$ on vertices at Level $2j-1$ of $\text{chain}(v)$
for each $j\in\\{1,2,\dots,\ell\\}$, $f_{1}^{*}$ restricted to the vertex set
of $\text{chain}(v)$ (i.e., ${f_{1}^{*}}_{\restriction{V(\text{chain}(v))}}$)
can be obtained from ${f_{2}^{*}}_{\restriction{V(\text{chain}(v))}}$ by
applying a permutation of colours on the set of vertices at Level $2j-1$ for
each $j\in\\{1,2,\dots,\ell\\}$. Since applying a permutation of colours on
the set of vertices at Level $2j-1$ for each $j\in\\{1,2,\dots,\ell\\}$
corresponds to an automorphism of $\text{chain}(v)$ (see Figure 2 in the
supplement for a demonstration), there exists an automorphism $\psi_{v}^{*}$
of $\text{chain}(v)$ such that
${f_{1}^{*}}_{\restriction{V(\text{chain}(v))}}={f_{2}^{*}}_{\restriction{V(\text{chain}(v))}}\circ\psi_{v}^{*}$.
Hence, $f_{1}^{*}(x)=f_{2}^{*}(\psi_{v}^{*}(x))$ for each $x\in
V(\text{chain}(v))$. Define $\psi_{v}\colon V(G^{*})\to V(G^{*})$ as
$\psi_{v}(x)=\psi_{v}^{*}(x)$ for each $x\in V(\text{chain}(v))$ and
$\psi_{v}(x)=x$ otherwise. Clearly, $f_{1}^{*}(x)=f_{2}^{*}(\psi_{v}(x))$ for
each $x\in V(\text{chain}(v))$. Define $\psi$ as the function composition of
$\psi_{v}$’s (i.e.,
$\psi=\psi_{v_{1}}\circ\psi_{v_{2}}\circ\dots\circ\psi_{v_{n}}$ if
$V(G)=\\{v_{1},v_{2},\dots,v_{v}\\}$). Since
$f_{1}^{*}(x)=f_{2}^{*}(\psi_{v}(x))$ for each $x\in V(\text{chain}(v))$ and
$\psi_{v}$ is an automorphism of $G^{*}$ that fixes vertices not in
$\text{chain}(v)$ for each $v\in V(G)$, we have
$f_{1}^{*}(x)=f_{2}^{*}(\psi(x))$ for each vertex $x$ in some chain gadget of
$G^{*}$. To prove that $f_{1}^{*}=f_{2}^{*}\circ\psi$, it suffices to show
that $f_{1}^{*}(x)=f_{2}^{*}(x)$ for each vertex $x$ of $G^{*}$ which is not
in any gadget; i.e., $x$ is a vertex of the form $e_{j}^{(t)}$ in Figure 10,
where $e^{(t)}=uv$ is an edge in $G$. Recall that the vertex $e_{j}^{(t)}$ is
adjacent to both $u_{vj}$ and $v_{uj}$ in $G^{*}$. For $i\in\\{1,2\\}$,
$\phi(f_{i}^{*})$ is a 3-colouring of $G^{*}$, and thus
$f_{i}^{*}(u_{vj})=(\phi(f_{i}^{*}))(u)\neq(\phi(f_{i}^{*}))(v)=f_{i}^{*}(v_{uj})$.
For $i\in\\{1,2\\}$, since $f_{i}^{*}(u_{vj})\neq f_{i}^{*}(v_{uj})$, the
colour of $e_{j}^{(t)}$ under $f_{i}^{*}$ is the unique colour in
$\\{0,1,2\\}\setminus\\{f_{i}^{*}(u_{vj}),f_{i}^{*}(v_{uj})\\}$. In other
words, the colour of $e_{j}^{(t)}$ under $f_{i}^{*}$ is the unique colour in
$\\{0,1,2\\}\setminus\\{(\phi(f_{i}^{*}))(u),(\phi(f_{i}^{*}))(v)\\}$. Since
$\phi(f_{1}^{*})=\phi(f_{2}^{*})$, the unique colour in
$\\{0,1,2\\}\setminus\\{(\phi(f_{1}^{*}))(u),(\phi(f_{1}^{*}))(v)\\}$ is the
same as the unique colour in
$\\{0,1,2\\}\setminus\\{(\phi(f_{2}^{*}))(u),(\phi(f_{2}^{*}))(v)\\}$. That
is, $f_{1}^{*}(e_{j}^{(t)})=f_{2}^{*}(e_{j}^{(t)})$. This completes the proof
of $f_{1}^{*}=f_{2}^{*}\circ\psi$, and thus proves Claim 5.

By Claim 4 and Claim 5, $\phi$ gives a bijection from the set of 3-acyclic
colourings of $G^{*}$ up to automorphisms to the set of 3-colourings of $G$.
Therefore, $\phi$ also gives a bijection from the set of 3-acyclic colourings
of $G^{*}$ up to colour swaps and automorphisms to the set of 3-colourings of
$G$ up to colour swaps. In particular, the number of 3-colourings of $G$ up to
colour swaps is equal to the number of 3-acyclic colourings of $G^{*}$ up to
colour swaps and automorphisms. This proves the guarantee. ∎

Let us consider the time complexity of Construction 5. Assume that
$V(G)=\\{v_{1},\allowbreak v_{2},\dots,v_{n}\\}$, where
$\deg_{G}(v_{1})\leq\deg_{G}(v_{2})\leq\dots\leq\deg_{G}(v_{n})$ and
$\lambda(v_{i})=i$ for $1\leq i\leq n$. Let $m=|E(G)|$. For $1\leq i\leq n$,
since $\text{chain}(v_{i})$ has $\deg_{G}(v_{i})+i$ terminals, there are at
most $5(\deg_{G}(v_{i})+i)\leq 5\deg_{G}(v_{i})+5n$ vertices and at most
$6(\deg_{G}(v_{i})+i)+2(\deg_{G}(v_{i})+i-1)\leq 8\deg_{G}(v_{i})+8n$ edges in
$\text{chain}(v_{i})$. There are $3m$ vertices and $6m$ edges that are not in
any chain gadget in $G^{\prime}$. Thus, in $G^{\prime}$, there are at most
$\left(\sum_{i=1}^{n}(5\deg_{G}(v_{i})+5n)\right)+3m\leq 10m+5n^{2}+3m\leq
18\,n^{2}$ vertices and
$\left(\sum_{i=1}^{n}(8\deg_{G}(v_{i})+8n)\right)+6m\leq 16m+8n^{2}+6m\leq
30\,n^{2}$ edges. Hence, Construction 5 requires only time polynomial in $n$.
Construction 5 establishes a reduction from the problem Another 3-Colouring
[$\mathcal{R}_{\text{swap}}$] ($\Delta=8$) to the problem Another 3-Acyclic
Colouring [$\mathcal{R}_{\text{swap+auto}}$] ($\Delta=4$). Since Another
3-Colouring [$\mathcal{R}_{\text{swap}}$] ($\Delta=8$) is NP-complete (see
page 1.4), we have the following theorem.

######  Theorem 10.

For bipartite graphs of maximum degree 4, Another 3-Acyclic Colouring
$[\mathcal{R}_{\text{swap+auto}}]$ is NP-complete, and thus Unique 3-Acyclic
Colouring $[\mathcal{R}_{\text{swap+auto}}]$ is coNP-hard. ∎

Observe that there is no universal vertex (i.e., a vertex adjacent to every
other vertex) in the output graph in Construction 5. Hence, we have the
following corollary.

######  Corollary 3.

Another 3-Acyclic Colouring $[\mathcal{R}_{\text{swap+auto}}]$ is NP-complete
for graphs without any universal vertex.

Next, we show that for $k\geq 4$, Another $k$-Acyclic Colouring
$[\mathcal{R}_{\text{swap+auto}}]$ is NP-complete.

Level 1Level 2Level 3Level 4Level $2t-1$Level $2t$. . . Figure 11: Chain
gadget in Construction 5.

$u_{1}$$u_{2}$$u_{q}$. . .$v_{1}$$v_{2}$$v_{n}$. . .$G$$K_{q}$ Figure 12:
Graph $G^{\prime}$ in Construction 6 (edges within the copy of $G$ are not
displayed).

###### Construction 6.

_Parameter:_ A positive integer $q$.
_Input:_ A graph $G$ without any universal vertex.
_Output:_ A graph $G^{\prime}$.
_Guarantee:_ $G$ has a unique 3-acyclic colouring up to colour swaps and
automorphisms if and only if $G^{\prime}$ has a unique $(q+3)$-acyclic
colouring up to colour swaps and automorphisms.
_Steps:_
Let $v_{1},v_{2},\dots,v_{n}$ be the vertices in $G$. Let $H$ be a graph
isomorphic to $K_{q}$ with vertex set $\\{u_{1},u_{2},\dots,u_{q}\\}$. To
construct $G^{\prime}$, introduce a copy of $G$ and a copy of $H$, and join
each $u_{j}$ to each $v_{i}$ for $1\leq i\leq n$ and $1\leq j\leq q$ (i.e.,
$G^{\prime}$ is the graph join of $G$ and $K_{q}$; see Figure 12).

###### Proof of Guarantee.

Let $U=\\{u_{1},u_{2},\dots,u_{q}\\}$ and $V=\\{v_{1},v_{2},\dots,v_{n}\\}$.
Since there is no universal vertex in $G$, the set $U$ is precisely the set of
universal vertices in $G^{\prime}$.

First, let us consider the structure of automorphisms of $G^{\prime}$. Let
$\psi^{\prime}$ be an automorphism of $G^{\prime}$. Since automorphisms
preserve the vertex degrees [32, Lemma 1.3.1], $\psi^{\prime}$ maps each
universal vertex in $G^{\prime}$ to a universal vertex in $G^{\prime}$ (i.e.,
$\psi^{\prime}(u_{j})\in U$ for all $u_{j}\in U$). Hence, $\psi^{\prime}$ maps
each vertex in $V$ to a vertex in $V$ (i.e., $\psi^{\prime}_{\restriction V}$
is a bijection from $V$ to itself). Since $\psi^{\prime}$ is an automorphism
of $G^{\prime}$ and its restriction to $V$ is a bijection from $V$ to itself,
$\psi^{\prime}$ restricted to $V$ is an automorphism of $G^{\prime}[V]$. Since
$G\cong G^{\prime}[V]$, we have the following.

###### Claim 1:

For every automorphism $\psi^{\prime}$ of $G^{\prime}$, the restriction of
$\psi^{\prime}$ to $V(G)$ is an automorphism of $G$.

In the reverse direction, let $\psi$ be an automorphism of $G$. Define
$\psi^{\prime}\colon V(G^{\prime})\to V(G^{\prime})$ as
$\psi^{\prime}(v_{i})=\psi(v_{i})$ for $1\leq i\leq n$ and
$\psi^{\prime}(u_{j})=u_{j}$ for $1\leq j\leq q$. Clearly, $\psi^{\prime}$ is
a bijection from $V(G^{\prime})$ to itself. Next, we show that $\psi^{\prime}$
preserves adjacency as well as non-adjacency. Since
$\psi=\psi^{\prime}_{\restriction V(G)}$, it is easy to verify that for $1\leq
i<j\leq n$, $\psi^{\prime}(v_{i})\psi^{\prime}(v_{j})\in E(G^{\prime})$ if and
only if $v_{i}v_{j}\in E(G^{\prime})$. Each $u_{j}\in U$ is a universal vertex
in $G^{\prime}$ and $\psi^{\prime}(u_{j})=u_{j}$; as a result, $u_{j}x\in
E(G^{\prime})$ and $\psi^{\prime}(u_{j})\psi^{\prime}(x)\in E(G^{\prime})$ for
all $x\in V(G^{\prime})$. Therefore, $\psi^{\prime}$ preserves adjacency as
well as non-adjacency, and thus $\psi^{\prime}$ is an automorphism of
$G^{\prime}$. Thus, we have the following claim.

###### Claim 2:

For every automorphism $\psi$ of $G$, the extension $\psi^{\prime}$ of $\psi$
into $V(G^{\prime})$ defined as $\psi^{\prime}(v_{i})=\psi(v_{i})$ for $1\leq
i\leq n$ and $\psi^{\prime}(u_{j})=u_{j}$ for $1\leq j\leq q$ is an
automorphism of $G^{\prime}$.

We are ready to prove the guarantee. Since $G^{\prime}$ is the graph join of
$K_{q}$ and $G$, we have
$\chi_{a}(G^{\prime})=\min\\{\chi_{a}(K_{q})+n,q+\chi_{a}(G)\\}$ by [46, Lemma
2.1] and thus
$\chi_{a}(G^{\prime})=\min\\{q+n,q+\chi_{a}(G)\\}=q+\chi_{a}(G)$. Hence, $G$
is 3-acyclic colourable if and only if $G^{\prime}$ is $(q+3)$-acyclic
colourable. To complete the proof of the guarantee, it suffices to prove the
following claim.

###### Claim 3:

$G$ has two 3-acyclic colourings $f_{1}$ and $f_{2}$ such that
$(f_{1},f_{2})\notin\mathcal{R}_{\text{swap+auto}}(G,3)$ if and only if
$G^{\prime}$ has two $(q+3)$-acyclic colourings $f^{\prime}_{1}$ and
$f^{\prime}_{2}$ such that
$(f^{\prime}_{1},f^{\prime}_{2})\notin\mathcal{R}_{\text{swap+auto}}(G^{\prime},q+3)$.

To prove Claim 3, suppose that $G$ admits two 3-acyclic colourings $f_{1}$ and
$f_{2}$ which are not the same up to colour swaps and automorphisms (i.e.,
$(f_{1},f_{2})\notin\mathcal{R}_{\text{swap+auto}}(G,3)$). Without loss of
generality, assume that $f_{1}$ and $f_{2}$ use colours $0,1$ and $2$. For
$\ell\in\\{1,2\\}$, define $f^{\prime}_{\ell}\colon V(G^{\prime})\to
V(G^{\prime})$ as $f^{\prime}_{\ell}(v_{i})=f_{\ell}(v_{i})$ for $1\leq i\leq
n$ and $f^{\prime}_{\ell}(u_{j})=j+2$ for $1\leq j\leq q$. Clearly,
$f^{\prime}_{1}$ and $f^{\prime}_{2}$ are $(q+3)$-colourings of $G^{\prime}$,
and $f_{\ell}={f^{\prime}_{\ell}}_{\,\restriction V(G)}$ for
$\ell\in\\{1,2\\}$. We claim that $f^{\prime}_{1}$ and $f^{\prime}_{2}$ are
not the same up to colour swaps and automorphisms. To produce a contradiction,
assume the contrary. That is, there exists a permutation $\sigma^{\prime}$ of
colours $0,1,\dots,q+2$ and an automorphism $\psi^{\prime}$ of $G^{\prime}$
such that
$f^{\prime}_{1}(\psi^{\prime}(x))=\sigma^{\prime}(f^{\prime}_{2}(x))$ for all
$x\in V(G^{\prime})$. Thus,
$f^{\prime}_{1}(\psi^{\prime}(u_{j}))=\sigma^{\prime}(f^{\prime}_{2}(u_{j}))$
for $1\leq j\leq q$, and
$f^{\prime}_{1}(\psi^{\prime}(v_{i}))=\sigma^{\prime}(f^{\prime}_{2}(v_{i}))$
for $1\leq i\leq n$. For $1\leq j\leq q$,
$f^{\prime}_{1}(\psi^{\prime}(u_{j}))=\sigma^{\prime}(j+2)$ since
$f^{\prime}_{2}(u_{j})=j+2$. Since $\psi^{\prime}$ is an automorphism of
$G^{\prime}$ and $U$ is the set of universal vertices in $G^{\prime}$,
$\psi^{\prime}$ maps vertices in $U$ to vertices in $U$. Thus, for each
$j\in\\{1,2,\dots,q\\}$, there exists a unique $\ell\in\\{1,2,\dots,q\\}$ such
that $\psi^{\prime}(u_{j})=u_{\ell}$. Since $f^{\prime}_{1}(u_{\ell})=\ell+2$
for $1\leq\ell\leq q$, this implies that for each $j\in\\{1,2,\dots,q\\}$,
there exists a unique $\ell\in\\{1,2,\dots,q\\}$ such that
$\sigma^{\prime}(j+2)=\ell+2$. That is, $\sigma^{\prime}$ restricted to
$\\{3,4,\dots,q+2\\}$ is a permutation of $\\{3,4,\dots,q+2\\}$. Hence,
$\sigma^{\prime}$ restricted to $\\{0,1,2\\}$ is a permutation of
$\\{0,1,2\\}$. Let $\sigma$ be the restriction of $\sigma^{\prime}$ to
$\\{0,1,2\\}$. Let $\psi=\psi^{\prime}_{\restriction V(G)}$. By Claim 1,
$\psi$ is an automorphism of $G$. Since
$\sigma=\sigma^{\prime}_{\restriction\\{0,1,2\\}}$,
$\psi=\psi^{\prime}_{\restriction V(G)}$,
$f_{\ell}={f^{\prime}_{\ell}}_{\,\restriction V(G)}$ and $f_{\ell}^{\prime}$
use only colours $0,1,2$ on $V(G)$ for $\ell\in\\{1,2\\}$, we can rewrite
“$f^{\prime}_{1}(\psi^{\prime}(v_{i}))=\sigma\,^{\prime}(f^{\prime}_{2}(v_{i}))$”
as “$f_{1}(\psi(v_{i}))=\sigma(f_{2}(v_{i}))$” for $1\leq i\leq n$. Since
$\sigma$ is a permutation of $\\{0,1,2\\}$ and $\psi$ is an automorphism of
$G$, $f_{1}$ and $f_{2}$ are the same up to colour swaps and automorphisms.
This is a contradiction. Thus, by contradiction, $f^{\prime}_{1}$ and
$f^{\prime}_{2}$ are not the same up to colour swaps and automorphisms.
Therefore, $G^{\prime}$ admits two $(q+3)$-acyclic colourings which are not
the same up to colour swaps and automorphisms.

Conversely, suppose that $G^{\prime}$ has two $(q+3)$-acyclic colourings
$f^{\prime}_{1}$ and $f^{\prime}_{2}$ that are not the same up to colour swaps
and automorphisms (i.e.,
$(f^{\prime}_{1},f^{\prime}_{2})\notin\mathcal{R}_{\text{swap+auto}}(G^{\prime},q+3)$).
Let $0,1,\dots,q+2$ be the colours used by $f^{\prime}_{1}$ and
$f^{\prime}_{2}$. For $\ell\in\\{1,2\\}$ and $1\leq j\leq q$, since $u_{j}$ is
a universal vertex in $G^{\prime}$, $u_{j}$ is the only vertex coloured
$f^{\prime}_{\ell}(u_{j})$ by $f^{\prime}_{\ell}$. Without loss of generality,
assume that $f^{\prime}_{1}(u_{j})=f^{\prime}_{2}(u_{j})=j+2$ for $1\leq j\leq
q$. Since each $u_{j}\in U$ is a universal vertex in $G^{\prime}$, we have
$f^{\prime}_{\ell}(v_{i})\in\\{0,1,2\\}$ for $\ell\in\\{1,2\\}$ and $1\leq
i\leq n$. For $\ell\in\\{1,2\\}$, let
$f_{\ell}={f^{\prime}_{\ell}}_{\,\restriction V(G)}$. Clearly,
$f_{\ell}(v_{i})\in\\{0,1,2\\}$ for $1\leq i\leq n$, and $f_{\ell}$ is a
3-colouring of $G$ for $\ell\in\\{1,2\\}$. For $\ell\in\\{1,2\\}$, since
$f_{\ell}$ is the restriction of an acyclic colouring to $V(G)$, $f_{\ell}$ is
an acyclic colouring of $G$. Hence, $f_{\ell}$ is a 3-acyclic colouring of $G$
for $\ell\in\\{1,2\\}$. We claim that $f_{1}$ and $f_{2}$ are not the same up
to colour swaps and automorphisms. To produce a contradiction, assume the
contrary. That is, there exists a permutation $\sigma$ of colours $0,1,2$ and
an automorphism $\psi$ of $G$ such that
$f_{1}(\psi(v_{i}))=\sigma(f_{2}(v_{i}))$ for $1\leq i\leq n$. Define a
permutation $\sigma^{\prime}$ of colours $0,1,\dots,q+2$ as
$\sigma^{\prime}(c)=\sigma(c)$ for $0\leq c\leq 2$ and $\sigma^{\prime}(c)=c$
for $3\leq c\leq q+2$. By Claim 2, the extension $\psi^{\prime}$ of $\psi$
into $V(G^{\prime})$ defined as $\psi^{\prime}(v_{i})=\psi(v_{i})$ for $1\leq
i\leq n$ and $\psi^{\prime}(u_{j})=u_{j}$ for $1\leq j\leq q$ is an
automorphism of $G^{\prime}$. For $1\leq j\leq q$,
$f^{\prime}_{1}(\psi^{\prime}(u_{j}))=\sigma^{\prime}(f^{\prime}_{2}(u_{j}))$
because $\psi^{\prime}(u_{j})=u_{j}$,
$f^{\prime}_{1}(u_{j})=f^{\prime}_{2}(u_{j})=j+2$ and
$\sigma^{\prime}(j+2)=j+2$. We know that
$f_{1}(\psi(v_{i}))=\sigma(f_{2}(v_{i}))$ for $1\leq i\leq n$. Since $\psi$,
$f_{1}$ and $f_{2}$ are restrictions of $\psi^{\prime}$, $f^{\prime}_{1}$ and
$f^{\prime}_{2}$ respectively to $V(G)$, and $\sigma$ is the restriction of
$\sigma^{\prime}$ to $\\{0,1,2\\}$, it follows that
$f^{\prime}_{1}(\psi^{\prime}(v_{i}))=\sigma^{\prime}(f_{2}^{\prime}(v_{i}))$
for $1\leq i\leq n$. Thus,
$f^{\prime}_{1}(\psi^{\prime}(x))=\sigma^{\prime}(f^{\prime}_{2}(x))$ for all
$x\in V(G^{\prime})$. That is, $f^{\prime}_{1}$ and $f^{\prime}_{2}$ are the
same up to colour swaps and automorphisms. This is a contradiction. Hence, by
contradiction, $f_{1}$ and $f_{2}$ are not the same up to colour swaps and
automorphisms. Therefore, $G$ admits two 3-acyclic colourings which are not
the same up to colour swaps and automorphisms. This completes the proof of
Claim 3. ∎

Let us consider the time complexity of Construction 6. Let $m=|E(G)|$.
Clearly, $G^{\prime}$ has only $n+q$ vertices and $m+nq+\binom{q}{2}\leq
m+nq+q^{2}$ edges. Since $q$ is fixed, Construction 6 requires only time
polynomial in the input size. By Corollary 3, Another 3-Acyclic Colouring
$[\mathcal{R}_{\text{swap+auto}}]$ is NP-complete for graphs without any
universal vertex. For each $q\in\mathbb{N}$, Construction 6 establishes a
reduction from this problem to Another $(q+3)$-Acyclic Colouring
$[\mathcal{R}_{\text{swap+auto}}]$. Thus, we have the following.

######  Theorem 11.

For $k\geq 4$, Another $k$-Acyclic Colouring
$[\mathcal{R}_{\text{swap+auto}}]$ is NP-complete, and thus Unique $k$-Acyclic
Colouring $[\mathcal{R}_{\text{swap+auto}}]$ is coNP-hard. ∎

We have the following theorem by combining Theorem 10 and Theorem 11.

######  Theorem 12.

For $k\geq 3$, Another $k$-Acyclic Colouring
$[\mathcal{R}_{\text{swap+auto}}]$ is NP-complete, and thus Unique $k$-Acyclic
Colouring $[\mathcal{R}_{\text{swap+auto}}]$ is coNP-hard. ∎

##  4 Open Problems and Related Works

Many problems related to acyclic colouring are open even for the class of
cubic graphs. Grünbaum [35] proved that cubic graphs are 4-acyclic colourable
(see also [59]). So, $3\leq\chi_{a}(G)\leq 4$ for every cubic graph $G$ which
is not a forest. Yet, it is unknown whether we can distinguish between the
cases $\chi_{a}(G)=3$ and $\chi_{a}(G)=4$ in polynomial time.

######  Problem 2 ([6]).

What is the complexity of 3-Acyclic Colourability in cubic graphs?

We know that there are infinitely many cubic graphs that are 3-acyclic
colourable and infinitely many that are not [6, Lemma 2]. Cheng et al. [19]
designed a polynomial-time algorithm that finds an optimal acyclic colouring
of a subcubic claw-free graph. They also proved that there are exactly three
subcubic claw-free graphs that require four colours for acyclic colouring.
Zhang and Bylka [63] proved that every cubic line graph except $K_{4}$ is
3-acyclic colourable. According to a conjecture of Zhu et al. [64], 3-Acyclic
Colourability is in P when restricted to cubic planar 3-connected graphs.

######  Conjecture 1 ([64]).

Every cubic planar 3-connected graph except $K_{4}$, $Q_{3}$ and the dual
graph of $P_{4}$ $\boxtimes$ $K_{2}$ $($see Figure 13$)$ is 3-acyclic
colourable.

Figure 13: The dual graph of $P_{4}$ $\boxtimes$ $K_{2}$, where  $\boxtimes$
denotes the graph join operation.

Regarding the class of bounded-degree graphs, the problem of determining the
exact value of $L_{a}^{(k)}$ for each $k\geq 3$ remains open. For $k\geq 4$,
finding the value of $L_{a}^{(k)}$ suffices to characterise the values $d$ for
which $k$-Acyclic Colourability in $d$-regular graphs is NP-complete (see
Theorem 7).

##  5 Acknowledgement

We thank Emil Jeřábek for his valuable comments.

## References

  * [1] Michael O. Albertson and David M. Berman.  An acyclic analogue to Heawood’s theorem.  Glasgow Mathematical Journal, 19:163–166, 1978.
  * [2] N. Alon and A. Zaks.  Algorithmic aspects of acyclic edge colorings.  Algorithmica, 32(4):611–614, 2002.
  * [3] Noga Alon, Colin McDiarmid, and Bruce Reed.  Acyclic coloring of graphs.  Random Structures & Algorithms, 2(3):277–288, 1991.
  * [4] Noga Alon, Bojan Mohar, and Daniel P. Sanders.  On acyclic colorings of graphs on surfaces.  Israel Journal of Mathematics, 94:273–283, 1996.
  * [5] Rogério G. Alves, Aldo Procacci, and Remy Sanchis.  Entropy compression versus Lovász local lemma.  Advances in Applied Mathematics, 125:32, 2021.  Id/No 102163.
  * [6] Patrizio Angelini and Fabrizio Frati.  Acyclically 3-colorable planar graphs.  Journal of Combinatorial Optimization, 24(2):116–130, 2012.
  * [7] Sanjeev Arora and Boaz Barak.  Computational complexity. A modern approach. Cambridge: Cambridge University Press, 2009.
  * [8] Manu Basavaraju and L. Sunil Chandran.  Acyclic edge coloring of 2-degenerate graphs.  Journal of Graph Theory, 69(1-2):1–27, 2012.
  * [9] Jan Bok, Nikola Jedlic̆ková, Barnaby Martin, Pascal Ochem, Daniel Paulusma, and Siani Smith.  Acyclic, star and injective colouring: a complexity picture for H-free graphs.  arXiv preprint arXiv:2008.09415, 2021.
  * [10] Jan Bok, Nikola Jedlic̆ková, Barnaby Martin, Daniël Paulusma, and Siani Smith.  Acyclic, star and injective colouring: a complexity picture for H-free graphs.  In 28th Annual European Symposium on Algorithms (ESA 2020), volume 173 of LIPIcs, pages 22:1–22:22, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  * [11] Richard B Borie, R Gary Parker, and Craig A Tovey.  Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families.  Algorithmica, 7(1-6):555–581, 1992.
  * [12] O. V. Borodin.  On acyclic colorings of planar graphs.  Discrete Mathematics, 25:211–236, 1979.
  * [13] O. V. Borodin.  Colorings of plane graphs: a survey.  Discrete Mathematics, 313(4):517–539, 2013.
  * [14] O. V. Borodin, Min Chen, Anna O. Ivanova, and A. Raspaud.  Acyclic 3-choosability of sparse graphs with girth at least 7.  Discrete Mathematics, 310(17-18):2426–2434, 2010.
  * [15] O.V. Borodin, A.V. Kostochka, A. Raspaud, and E. Sopena.  Acyclic colouring of 1-planar graphs.  Discrete Applied Mathematics, 114(1-3):29–41, 2001.
  * [16] Christoph Brause, Petr Golovach, Barnaby Martin, Pascal Ochem, Daniël Paulusma, and Siani Smith.  Acyclic, star, and injective colouring: bounding the diameter.  The Electronic Journal of Combinatorics, 29(2):p2.43, 29, 2022.
  * [17] M. I. Burstein.  Every 4-valent graph has an acyclic 5-colouring.  Soobshcheniya Akademii Nauk Gruzinskoĭ SSR, 93:21–24, 1979\.
  * [18] Jiansheng Cai, Binlu Feng, and Guiying Yan.  Acyclic coloring of graphs with some girth restriction.  Journal of Combinatorial Optimization, 31(4):1399–1404, 2016.
  * [19] Christine Cheng, Eric McDermid, and Ichiro Suzuki.  Planarization and acyclic colorings of subcubic claw-free graphs.  In Graph-theoretic concepts in computer science. 37th international workshop, WG 2011, Teplá Monastery, Czech Republic, June 21–24, 2011. Revised papers, pages 107–118. Berlin: Springer, 2011.
  * [20] Thomas F Coleman and Jin-Yi Cai.  The cyclic coloring problem and estimation of sparse Hessian matrices.  SIAM Journal on Algebraic Discrete Methods, 7(2):221–235, 1986\.
  * [21] Bruno Courcelle.  The monadic second-order logic of graphs. I. recognizable sets of finite graphs.  Information and Computation, 85(1):12–75, 1990.
  * [22] Ágnes Cseh and Telikepalli Kavitha.  Popular matchings in complete graphs.  Algorithmica, 83(5):1493–1523, 2021.
  * [23] David P. Dailey.  Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete.  Discrete Mathematics, 30:289–293, 1980.
  * [24] Thomas Emden-Weinert, Stefan Hougardy, and Bernd Kreuter.  Uniquely colourable graphs and hardness of colouring graphs of large girth.  Combinatorics, Probability and Computing, 7(4):375–386, 1998\.
  * [25] Guillaume Fertin, Emmanuel Godard, and André Raspaud.  Acyclic and $k$-distance coloring of the grid.  Information Processing Letters, 87(1):51–58, 2003.
  * [26] Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.  Kernelization. Theory of parameterized preprocessing.  Cambridge: Cambridge University Press, 2019.
  * [27] Robert Ganian and Petr Hliněný.  On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width.  Discrete Applied Mathematics, 158(7):851–867, 2010.
  * [28] Michael R Garey and David S Johnson.  Computers and Intractability, volume 29.  W. H. Freeman New York, 2002.
  * [29] Assefaw H Gebremedhin, Arijit Tarafdar, Fredrik Manne, and Alex Pothen.  New acyclic and star coloring algorithms with application to computing Hessians.  SIAM Journal on Scientific Computing, 29(3):1042–1072, 2007.
  * [30] Assefaw H. Gebremedhin, Arijit Tarafdar, Alex Pothen, and Andrea Walther.  Efficient computation of sparse Hessians using coloring and automatic differentiation.  INFORMS Journal on Computing, 21(2):209–223, 2009.
  * [31] Assefaw Hadish Gebremedhin, Fredrik Manne, and Alex Pothen.  What color is your Jacobian? Graph coloring for computing derivatives.  SIAM Review, 47(4):629–705, 2005.
  * [32] Chris Godsil and Gordon Royle.  Algebraic graph theory, volume 207.  New York, NY: Springer, 2001.
  * [33] Daniel Gonçalves, Mickael Montassier, and Alexandre Pinlou.  Acyclic coloring of graphs and entropy compression method.  Discrete Mathematics, 343(4):13, 2020.  Id/No 111772.
  * [34] Isaac Grosof.  Is there a planar 4-regular graph that is 3-acyclic colourable?  Theoretical Computer Science Stack Exchange, 2020.  (URL version: 2020-06-10), Author URL: https://cstheory.stackexchange.com/users/25504/isaacg.
  * [35] Branko Grünbaum.  Acyclic colorings of planar graphs.  Israel Journal of Mathematics, 14:390–408, 1973.
  * [36] Tommy R. Jensen and Bjarne Toft.  Graph coloring problems.  New York, NY: John Wiley & Sons, 1995.
  * [37] Jiansheng Cai Juan Wang, Zuosong Liang and Lianying Miao.  Acyclic coloring of claw-free graphs with small degree.  Discrete Applied Mathematics, 321:272–280, 2022.
  * [38] Ilan Karpas, Ofer Neiman, and Shakhar Smorodinsky.  On vertex rankings of graphs and its relatives.  Discrete Mathematics, 338(8):1460–1467, 2015.
  * [39] Ken-Ichi Kawarabayashi and Bojan Mohar.  Star coloring and acyclic coloring of locally planar graphs.  SIAM Journal on Discrete Mathematics, 24(1):56–71, 2010.
  * [40] Lefteris Kirousis and John Livieratos.  Improved bounds for acyclic coloring parameters.  arXiv preprint arXiv:2202.13846, 2022.
  * [41] Alexandr V Kostochka.  Upper bounds of chromatic functions of graphs.  PhD thesis, Novosibirsk, 1978.
  * [42] Alexandr V. Kostochka and Christopher Stocker.  Graphs with maximum degreee 5 are acyclically 7-colorable.  Ars Mathematica Contemporanea, 4(1):153–164, 2011.
  * [43] Richard E. Ladner.  On the structure of polynomial time reducibility.  Journal of the Association for Computing Machinery, 22:155–171, 1975.
  * [44] Daniel Leven and Zvi Galil.  NP-completeness of finding the chromatic index of regular graphs.  Journal of Algorithms, 4:35–44, 1983.
  * [45] Cláudia Linhares-Sales, Ana Karolinna Maia, Nicolas Martins, and Rudini M. Sampaio.  Restricted coloring problems on graphs with few $P_{4}$’s.  Annals of Operations Research, 217:385–397, 2014.
  * [46] Andrew Lyons.  Acyclic and star colorings of cographs.  Discrete Applied Mathematics, 159(16):1842–1850, 2011.
  * [47] Yulai Ma, Yongtang Shi, and Weifan Wang.  Acyclic edge coloring of chordal graphs with bounded degree.  Graphs and Combinatorics, 37(6):2621–2636, 2021.
  * [48] Mikero.  Parameterized complexity from P to NP-hard and back again.  Theoretical Computer Science Stack Exchange, 2010.  (URL version: 2017-04-13), Author URL: https://cstheory.stackexchange.com/users/149/mikero.
  * [49] Michael Molloy and Bruce Reed.  Colouring graphs when the number of colours is almost the maximum degree.  Journal of Combinatorial Theory. Series B, 109:134–195, 2014\.
  * [50] Debajyoti Mondal, Rahnuma Islam Nishat, Md. Saidur Rahman, and Sue Whitesides.  Acyclic coloring with few division vertices.  Journal of Discrete Algorithms, 23:42–53, 2013.
  * [51] Rahul Muthu, N. Narayanan, and C. R. Subramanian.  Improved bounds on acyclic edge colouring.  Discrete Mathematics, 307(23):3063–3069, 2007.
  * [52] Sokol Ndreca, Aldo Procacci, and Benedetto Scoppola.  Improved bounds on coloring of graphs.  European Journal of Combinatorics, 33(4):592–609, 2012.
  * [53] Rolf Niedermeier.  Invitation to fixed parameter algorithms., volume 31 of Oxf. Lect. Ser. Math. Appl. Oxford: Oxford University Press, 2006.
  * [54] Pascal Ochem.  Negative results on acyclic improper colorings.  In 2005 European conference on combinatorics, graph theory and applications (EuroComb ’05), pages 357–362. Paris: Maison de l’Informatique et des Mathématiques Discrétes (MIMD), 2005.
  * [55] Vangelis Th. Paschos, editor.  Combinatorial optimization. Volume 1: Concepts of combinatorial optimization. London: ISTE; Hoboken, NJ: John Wiley & Sons, 2010.
  * [56] Daniël Paulusma.  Open problems on graph coloring for special graph classes.  In Graph-theoretic concepts in computer science. 41st international workshop, WG 2015, Garching, Germany, pages 16–30. Berlin: Springer, 2016.
  * [57] Jean-Sébastien Sereni and Jan Volec.  A note on acyclic vertex-colorings.  Journal of Combinatorics, 7(4):725–737, 2016.
  * [58] M A Shalu and Cyriac Antony.  Star colouring of bounded degree graphs and regular graphs.  Discrete Mathematics, 345(6):112850, 2022.
  * [59] San Skulrattanakulchai.  Acyclic colorings of subcubic graphs.  Information Processing Letters, 92(4):161–167, 2004.
  * [60] Tao Wang and Yaqiong Zhang.  Acyclic edge coloring of graphs.  Discrete Applied Mathematics, 167:290–303, 2014.
  * [61] Douglas Brent West.  Introduction to graph theory.  Prentice Hall, Upper Saddle River, 2nd edition, 2001.
  * [62] Wanshun Yang, Weifan Wang, and Yiqiao Wang.  An improved upper bound for the acyclic chromatic number of 1-planar graphs.  Discrete Applied Mathematics, 283:275–291, 2020.
  * [63] Xiao-Dong Zhang and Stanislaw Bylka.  Disjoint triangles of a cubic line graph.  Graphs and Combinatorics, 20(2):275–280, 2004.
  * [64] Enqiang Zhu, Zepeng Li, Zehui Shao, Jin Xu, and Chanjuan Liu.  Acyclic 3-coloring of generalized Petersen graphs.  Journal of Combinatorial Optimization, 31(2):902–911, 2016.