# Acyclic, star and injective colouring: A complexity picture for H-free graphs

Jan Bok, Nikola Jedličková, Barnaby Martin, Pascal Ochem, Daniël Paulusma, Siani Smith

► To cite this version:

Jan Bok, Nikola Jedličková, Barnaby Martin, Pascal Ochem, Daniël Paulusma, et al. Acyclic, star and injective colouring: A complexity picture for H-free graphs. Journal of Computer and System Sciences, 2025, 154, pp.103662. 10.1016/j.jcss.2025.103662. lirmm-05124700

HAL Id: lirmm-05124700

https://hal-lirmm.ccsd.cnrs.fr/lirmm-05124700v1

Submitted on 22 Jun 2025

**HAL** is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire **HAL**, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Acyclic, star and injective colouring: A complexity picture for $H$-free graphs ⭐

<figure><img src="image_2.png" /></figure>

Check for
updates

Jan Bok<sup>a, 1</sup>, Nikola Jedličková<sup>b, 2</sup>, Barnaby Martin<sup>c</sup>, Pascal Ochem<sup>d</sup>, Daniël Paulusma<sup>c, *, 3</sup>, Siani Smith<sup>c</sup>

## ARTICLE INFO

**Article history:**

Received 10 May 2021

Received in revised form 26 August 2024

Accepted 24 April 2025

Available online 5 May 2025

**Keywords:**

Acyclic colouring

Star colouring

Injective colouring

$H$-free

Dichotomy

## ABSTRACT

A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are ACYCLIC COLOURING, STAR COLOURING and INJECTIVE COLOURING. We give almost complete complexity classifications for ACYCLIC COLOURING, STAR COLOURING and INJECTIVE COLOURING on $H$-free graphs (for each of the problems, we have one open case). Moreover, we give full complexity classifications if the number of colours $k$ is fixed, that is, not part of the input. From our study it follows that for fixed $k$, the three problems behave in the same way, but this is no longer true if $k$ is part of the input. To obtain several of our results we prove stronger complexity results that in particular involve the girth of a graph and the class of line graphs of multigraphs.

© 2025 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

## 1. Introduction

We study the complexity of three classical colouring problems. We do this by focusing on hereditary graph classes, i.e., classes closed under vertex deletion. Examples of well-known hereditary graph classes are the classes of bipartite graphs, chordal graphs, claw-free graphs, perfect graphs, planar graphs and so on. Hereditary graph classes are exactly those graph classes that can be characterized by a (possibly infinite) set $\mathcal{F}$ of forbidden induced subgraphs. For example, for the class of bipartite graphs, the set $\mathcal{F}$ consists of all odd cycles. Ideally, we would like to determine the complexity of a problem for every hereditary graph class. However, as evidenced by numerous complexity studies in the literature, even the case where $|\mathcal{F}| = 1$ is often already highly challenging but at the same time also captures a rich family of graph classes suitably

<footnote><sup>a</sup> Computer Science Institute, Charles University, Prague, Czech Republic</footnote>

<footnote><sup>b</sup> Department of Applied Mathematics, Charles University, Prague, Czech Republic</footnote>

<footnote><sup>c</sup> Department of Computer Science, Durham University, Durham, United Kingdom</footnote>

<footnote><sup>d</sup> LIRMM, CNRS, Université de Montpellier, Montpellier, France</footnote>

<footnote>☆ Extended abstracts of this paper are in the proceedings of ESA 2020 [10] and CSR 2021 [11].</footnote>

<footnote>* Corresponding author.</footnote>

<footnote>E-mail addresses: bok@iuuk.mff.cuni.cz (J. Bok), jedlickova@kam.mff.cuni.cz (N. Jedličková), barnaby.d.martin@durham.ac.uk (B. Martin), ochem@lirmm.fr (P. Ochem), daniel.paulusma@durham.ac.uk (D. Paulusma), siani.smith@durham.ac.uk (S. Smith).</footnote>

<footnote n="1">¹ Supported by GAUK 1580119, SVV-2020-260578, and by The European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 810115 - DYNASNET).</footnote>

<footnote n="2">² Supported by GAUK 1198419 and SVV-2020-260578.</footnote>

<footnote n="3">³ Supported by the Leverhulme Trust (RPG-2016-258).</footnote>
interesting to develop general methodology. Hence, we usually first set $\mathcal{F} = \{H\}$ and consider the class of *H-free* graphs, i.e., graphs that do not contain *H* as an induced subgraph. We then investigate how the complexity of a problem restricted to *H-free* graphs depends on the choice of *H* and try to obtain a *complexity dichotomy*. This is also the approach we follow in this paper.

To give a well-known and relevant example, the COLOURING problem is to decide, given a graph $G$ and integer $k \ge 1$, if $G$ has a *k-colouring*, i.e., a mapping $c: V(G) \to \{1, \dots, k\}$ such that $c(u) \ne c(v)$ for every two adjacent vertices $u$ and $v$. Král' et al. [49] proved that COLOURING on *H-free* graphs is polynomial-time solvable if $H$ is an induced subgraph of $P_4$ or $P_1 + P_3$ and NP-complete otherwise. Here, $P_n$ denotes the $n$-vertex path and $G_1+G_2 = (V(G_1) \cup V(G_2), E(G_1) \cup E(G_2))$ the disjoint union of two vertex-disjoint graphs $G_1$ and $G_2$. If $k$ is fixed (not part of the input), then we obtain the *k-COLOURING* problem. No complexity dichotomy is known for *k-COLOURING* if $k \ge 3$. In particular, the complexities of 3-COLOURING for $P_t$-free graphs for $t \ge 8$ and *k*-COLOURING for $(P_4+sP_2)$-free graphs for $s \ge 1$ and $k \ge 4$ are still open. Here, we write $sG$ for the disjoint union of $s$ copies of $G$. We refer to the survey of Golovach et al. [35] for further details and to [18,19,47] for updated summaries.

For a colouring $c$ of a graph $G$, a *colour class* consists of all vertices of $G$ that are mapped by $c$ to a specific colour $i$. We consider the following special graph colourings. A colouring of a graph $G$ is *acyclic* if the union of any two colour classes induces a forest. The $(r+1)$-vertex star $K_{1,r}$ is the graph with vertices $u, v_1, \dots, v_r$ and edges $uv_i$ for every $i \in \{1, \dots, r\}$. An acyclic colouring is a *star colouring* if the union of any two colour classes induces a *star forest*, that is, a forest in which each connected component is a star. A star colouring is *injective* (or an $L(1, 1)$-labelling or a *distance-2 colouring*) if the union of any two colour classes induces an $sP_1 + tP_2$ for some integers $s \ge 0$ and $t \ge 0$. An alternative definition is to say that all the neighbours of every vertex of $G$ are uniquely coloured. For example, the 4-vertex cycle $C_4$ has a *k-colouring* for $2 \le k \le 4$; an acyclic *k-colouring* and star *k-colouring* for $3 \le k \le 4$ and an injective *k-colouring* for $k=4$, whereas the 4-vertex path $P_4$ has a *k-colouring* and acyclic *k-colouring* for $2 \le k \le 4$; and a star *k-colouring* and injective *k-colouring* for $3 \le k \le 4$. The above definitions lead to the following three well-known decision problems:

**ACYCLIC COLOURING**

*Instance:* A graph $G$ and an integer $k \ge 1$

*Question:* Does $G$ have an acyclic *k*-colouring?

**STAR COLOURING**

*Instance:* A graph $G$ and an integer $k \ge 1$

*Question:* Does $G$ have a *star* *k*-colouring?

**INJECTIVE COLOURING**

*Instance:* A graph $G$ and an integer $k \ge 1$

*Question:* Does $G$ have an injective *k*-colouring?

If $k$ is fixed, we write *ACYCLIC K-COLOURING*, *STAR K-COLOURING* and *INJECTIVE K-COLOURING*, respectively. We note that in the literature on the *INJECTIVE COLOURING* problem it is often assumed that two adjacent vertices may be coloured alike by an injective colouring (see, for example, [38,39,44]). However, in our paper, we do **not** allow this; as reflected in their definitions we only consider colourings that are proper. This enables us to compare the results for the three different kinds of colourings with each other.

All three colouring variants have been extensively studied, as they form a framework in which natural additional conditions are imposed on the bipartite subgraph introduced by two colour classes corresponding to some graph colouring; see also the paper of Grünbaum [37], who introduced the notions of acyclic colouring and star colouring in 1973.

However, so far, systematic studies for the latter two variants mainly focused on structural characterizations, exact values, lower and upper bounds on the minimum number of colours in an acyclic colouring or star colouring (i.e., the *acyclic* and *star chromatic number*); see, e.g., [4,13,26,28,29,45,46,63,64,66], to name just a few papers. Injective colourings (and the *injective chromatic number*) were mainly considered in the context of the distance constrained labelling framework related to frequency assignment (see the survey [16] and Section 6 therein). Nevertheless, the three colouring variants have also been studied from a complexity perspective, but apart from a study on *ACYCLIC COLOURING* for graphs of bounded maximum degree [59], known results are scattered and relatively sparse. We therefore perform a *systematic* and *comparative* complexity study by focusing on the following research question both for *k* part of the input and for fixed *k*:

*What are the computational complexities of ACYCLIC COLOURING, STAR COLOURING and INJECTIVE COLOURING for H-free graphs?*

**Known Results**

Before discussing our new results and techniques, we first briefly discuss some known results, several of which will play an important role in our paper.
**Known Hardness Results.** We first present some relevant NP-completeness results for ACYCLIC COLOURING, STAR COLOURING and INJECTIVE COLOURING, respectively.

Coleman and Cai [20] proved that for every $k \ge 3$, ACYCLIC $k$-COLOURING is NP-complete for bipartite graphs. Afterwards, a number of hardness results appeared for other hereditary graph classes. Alon and Zaks [5] showed that ACYCLIC 3-COLOURING is NP-complete for line graphs of maximum degree 4. Kostochka [48] proved that ACYCLIC 3-COLOURING is NP-complete for planar graphs. This result was improved to planar bipartite graphs of maximum degree 4 by Ochem [60]. Mondal et al. [59] proved that ACYCLIC 4-COLOURING is NP-complete for graphs of maximum degree 5 and for planar graphs of maximum degree 7. Ochem [60] showed that ACYCLIC 4-COLOURING is NP-complete for planar bipartite graphs of maximum degree 8. We refer to the paper of Angelini and Frati [6] for a further discussion on acyclic colourable planar graphs.

Albertson et al. [1] and recently, Lei et al. [51] proved that STAR 3-COLOURING is NP-complete for planar bipartite graphs and line graphs, respectively. Shalu and Antony [62] showed that STAR COLOURING is NP-complete for co-bipartite graphs.

Bodlaender et al. [9], Sen and Huson [61] and Lloyd and Ramanathan [54] proved that INJECTIVE COLOURING is NP-complete for split graphs, unit disk graphs and planar graphs, respectively. Mahdian [58] proved that for every $k \ge 4$, INJECTIVE $k$-COLOURING is NP-complete for line graphs, whereas INJECTIVE 4-COLOURING is also known to be NP-complete for cubic graphs (see [16]). Observe that INJECTIVE 3-COLOURING is trivial for general graphs.

**Known Polynomial Results.** We now state some relevant polynomial results for ACYCLIC COLOURING, STAR COLOURING and INJECTIVE COLOURING.

Lyons [56] proved that ACYCLIC COLOURING and STAR COLOURING are polynomial-time solvable for $P_4$-free graphs; in particular, he showed that every acyclic colouring of a $P_4$-free graph is, in fact, a star colouring. We note that INJECTIVE COLOURING is trivial for $P_4$-free graphs, as every injective colouring must assign each vertex of a connected $P_4$-free graph a unique colour. Afterwards, the results of Lyons have been extended to $P_4$-tidy graphs and $(q, q-4)$-graphs by Linhares-Sales et al. [53].

Cheng et al. [17] complemented the aforementioned result of Alon and Zaks [5] by proving that ACYCLIC COLOURING is polynomial-time solvable for claw-free graphs of maximum degree at most 3. Calamoneri [16] observed that INJECTIVE COLOURING is polynomial-time solvable for comparability and co-comparability graphs. Zhou et al. [65] proved that INJECTIVE COLOURING is polynomial-time solvable for graphs of bounded treewidth (which is best possible due to the W[1]-hardness result of Fiala et al. [30]).

Finally, we refer to [14] for a recent complexity study of ACYCLIC COLOURING, STAR COLOURING and INJECTIVE COLOURING for graphs of bounded diameter.

**Our Complexity Results and Methodology**

The girth of a graph $G$ is the length of a shortest cycle of $G$ (if $G$ is a forest, then its girth is $\infty$). To answer our research question we focus on two important graph classes, namely the classes of graphs of high girth and line graphs of multigraphs, which are interesting classes on their own. If a problem is NP-complete for both classes, then it is NP-complete for H-free graphs whenever $H$ has a cycle or a claw. It then remains to analyze the case when $H$ is a linear forest, i.e., a disjoint union of paths; see [12,15,33,49] for examples of this approach, which we discuss in detail below.

The construction of graph families of high girth and large chromatic number is well studied in graph theory (see, e.g. [25]). To prove their complexity dichotomy for COLOURING on H-free graphs, Král' et al. [49] first showed that for every integer $g \ge 3$, 3-COLOURING is NP-complete for the class of graphs of girth at least $g$. This approach can be readily extended to any integer $k \ge 3$ [24,55]. The basic idea is to replace edges in a graph by graphs of high girth and large chromatic number, such that the resulting graph has sufficiently high girth and is $k$-colourable if and only if the original graph is so (see also [36,41]).

By a more intricate use of the above technique we are able to prove that for every $g \ge 3$ and every $k \ge 3$, ACYCLIC $k$-COLOURING is NP-complete for the class of 2-degenerate bipartite graphs of girth at least $g$. This implies that ACYCLIC $k$-COLOURING is NP-complete for H-free graphs whenever $H$ has a cycle. We are also able to prove that for every $g \ge 3$, STAR 3-COLOURING remains NP-complete even for planar graphs of girth at least $g$ and maximum degree 3. This implies that STAR 3-COLOURING is NP-complete for H-free graphs whenever $H$ has a cycle. We prove the latter result for every $k \ge 4$ by combining known results, just as we use known results to prove that INJECTIVE $k$-COLOURING ($k \ge 4$) is NP-complete for H-free graphs if $H$ has a cycle.

A classical result of Holyer [40] is that 3-COLOURING is NP-complete for line graphs (and Leven and Galil [52] proved the same for $k \ge 4$). As line graphs are claw-free, Král' et al. [49] used Holyer's result to show that 3-COLOURING is NP-complete for H-free graphs whenever $H$ has an induced claw. For ACYCLIC $k$-COLOURING, we can use Alon and Zaks' result [5] for $k=3$, which we extend to work for $k \ge 4$. For STAR $k$-COLOURING we extend the recent result of Lei et al. [51] from $k=3$ to $k \ge 3$ (in both our results we consider line graphs of multigraphs; these graphs are claw-free and hence suffice for our study on H-free graphs). For INJECTIVE $k$-COLOURING ($k \ge 4$) we can use the aforementioned result on line graphs of Mahdian [58].

The above hardness results leave us to consider the case where $H$ is a linear forest. In Section 2 we will use a result of Atminas et al. [7] to prove a general result from which it follows that for fixed $k$, all three problems are polynomial-time solvable for H-free graphs if $H$ is a linear forest. Hence, we have full complexity dichotomies for the three problems when $k$ is fixed. However, these positive results do not extend to the case where $k$ is part of the input. That is, for each of the three
<caption>**Table 1**</caption>

The state-of-the-art for the three problems in this paper and the original COLOURING problem; both when *k* is fixed and part of the input. The unreferenced results are the results listed in Theorems 1–3. The only open case for ACYCLIC COLOURING and STAR COLOURING is $H = 2P_2$. The only open case for INJECTIVE COLOURING is $H = 2P_1 + P_4$.

<table><thead><tr><th></th><th>Polynomial time</th><th>NP-complete</th></tr></thead><tbody><tr><td>COLOURING [49]</td><td>$H \subseteq_i P_4$ or $P_1 + P_3$</td><td>else</td></tr><tr><td>ACYCLIC COLOURING</td><td>$H \subseteq_i P_4$</td><td>else except for 1 open case: $H = 2P_2$</td></tr><tr><td>STAR COLOURING</td><td>$H \subseteq_i P_4$</td><td>else except for 1 open case: $H = 2P_2$</td></tr><tr><td>INJECTIVE COLOURING</td><td>$H \subseteq_i 2P_1 + P_4$</td><td>else except for 1 open case: $H = 2P_1 + P_4$</td></tr><tr><td>k-COLOURING (see [19,35,47])</td><td>depends on k</td><td>infinitely many open cases for all $k \ge 3$</td></tr><tr><td>ACYCLIC k-COLOURING ($k \ge 3$)</td><td>$H$ is a linear forest</td><td>else</td></tr><tr><td>STAR k-COLOURING ($k \ge 3$)</td><td>$H$ is a linear forest</td><td>else</td></tr><tr><td>INJECTIVE k-COLOURING ($k \ge 4$)</td><td>$H$ is a linear forest</td><td>else</td></tr></tbody></table>

problems, we prove NP-completeness for graphs that are $P_r$-free for some small value of $r$ or have a small independence number, i.e., that are $sP_1$-free for some small integer $s$.

Our complexity results for H-free graphs are summarized in the following three theorems, proven in Sections 3–5, respectively; see Table 1 for a comparison. For two graphs F and G, we write $F \subseteq_i G$ or $G \supseteq_i F$ to denote that F is an induced subgraph of G.

**Theorem 1.** Let H be a graph. For the class of H-free graphs it holds that:

(i) ACYCLIC COLOURING is polynomial-time solvable if $H \subseteq_i P_4$ and NP-complete if $H \not\subseteq_i P_4$ and $H \neq 2P_2$;

(ii) for every $k \ge 3$, ACYCLIC k-COLOURING is polynomial-time solvable if H is a linear forest and NP-complete otherwise.

**Theorem 2.** Let H be a graph. For the class of H-free graphs it holds that:

(i) STAR COLOURING is polynomial-time solvable if $H \subseteq_i P_4$ and NP-complete if $H \not\subseteq_i P_4$ and $H \neq 2P_2$;

(ii) for every $k \ge 3$, STAR k-COLOURING is polynomial-time solvable if H is a linear forest and NP-complete otherwise.

**Theorem 3.** Let H be a graph. For the class of H-free graphs it holds that:

(i) INJECTIVE COLOURING is polynomial-time solvable if $H \subseteq_i 2P_1 + P_4$ and NP-complete if $H \not\subseteq_i 2P_1 + P_4$;

(ii) for every $k \ge 4$, INJECTIVE k-COLOURING is polynomial-time solvable if H is a linear forest and NP-complete otherwise.

In Section 6 we give a number of open problems that resulted from our systematic study; in particular we will discuss the distance constrained labelling framework in more detail.

## 2. A general polynomial result

A biclique or complete bipartite graph is a bipartite graph on vertex set $S \cup T$, such that S and T are independent sets and there is an edge between every vertex of S and every vertex of T; if $|S| = s$ and $|T| = t$, we denote this graph by $K_{s,t}$, and if $s = t$, the biclique is balanced and of order $s$. We say that a colouring $c$ of a graph $G$ satisfies the balanced biclique condition (BB-condition) if $c$ uses at least $k + 1$ colours to colour $G$, where $k$ is the order of a largest biclique that is contained in $G$ as a (not necessarily induced) subgraph.

Let $\pi$ be some colouring property; e.g., $\pi$ could mean being acyclic, star or injective. Then $\pi$ can be expressed in $MSO_2$ (monadic second-order logic with edge sets) if for every $k \ge 1$, the graph property of having a k-colouring with property $\pi$ can be expressed in $MSO_2$. The general problem COLOURING ($\pi$) is to decide, on a graph $G$ and integer $k \ge 1$, if $G$ has a k-colouring with property $\pi$. If $k$ is fixed, we write $k$-COLOURING($\pi$). We now prove the following result.

**Theorem 4.** Let H be a linear forest, and let $\pi$ be a colouring property that can be expressed in $MSO_2$, such that every colouring with property $\pi$ satisfies the BB-condition. Then, for every integer $k \ge 1$, k-COLOURING($\pi$) is linear-time solvable for H-free graphs.

**Proof.** Atminas, Lozin and Razgon [7] proved that for every pair of integers $\ell$ and $k$, there exists a constant $b(\ell, k)$ such that every graph of treewidth at least $b(\ell, k)$ contains an induced $P_\ell$ or a (not necessarily induced) biclique $K_{k,k}$. Let $G$ be an H-free graph, and let $\ell$ be the smallest integer such that $H \subseteq_i P_\ell$; observe that $\ell$ is a constant. Hence, we can use Bodlaender's algorithm [8] to test in linear time if $G$ has treewidth at most $b(\ell, k) - 1$.

First suppose that the treewidth of $G$ is at most $b(\ell, k) - 1$. As $\pi$ can be expressed in $MSO_2$, the result of Courcelle [21] allows us to test in linear time whether $G$ has a k-colouring with property $\pi$. Now suppose that the treewidth of $G$ is at least $b(\ell, k)$. As $G$ is H-free, $G$ is $P_\ell$-free. Then, by the result of Atminas, Lozin and Razgon [7], we find that $G$ contains $K_{k,k}$ as a subgraph. As $\pi$ satisfies the BB-condition, $G$ has no k-colouring with property $\pi$. □
We now apply Theorem 4 to obtain the polynomial cases for fixed $k$ in Theorem 1–3.

**Corollary 5.** Let $H$ be a linear forest. For every $k \ge 1$, ACYCLIC $k$-COLOURING, STAR $k$-COLOURING and INJECTIVE $k$-COLOURING are polynomial-time solvable for $H$-free graphs.

**Proof.** All three kinds of colourings use at least $s$ colours to colour $K_{s,s}$ (as the vertices from one bipartition class of $K_{s,s}$ must receive unique colours). Hence, every acyclic, star and injective colouring of every graph satisfies the BB-condition. Moreover, it is readily seen that the colouring properties of being acyclic, star or injective can all be expressed in $\text{MSO}_2$. Hence, we may apply Theorem 4. □

**3. Acyclic colouring**

In this section, we prove Theorem 1. For a graph $G$ and a colouring $c$, the pair $(G, c)$ has a bichromatic cycle $C$ if $C$ is a cycle of $G$ with $|c(V(C)| = 2$, that is, the vertices of $C$ are coloured by two alternating colours (so $C$ is even). The notion of a bichromatic path is defined in a similar matter.

**Lemma 6.** For every $k \ge 3$ and every $g \ge 3$, ACYCLIC $k$-COLOURING is NP-complete for 2-degenerate bipartite graphs of girth at least $g$.

**Proof.** We reduce from ACYCLIC $k$-COLOURING, which is known to be NP-complete for bipartite graphs for every $k \ge 3$ [20]. Recall that the arboricity of a graph is the minimum number of forests needed to partition its edge set. By counting the edges, a graph with arboricity at most $t$ is $(2t - 1)$-degenerate and thus $2t$-colourable. We start by taking a graph $F$ that has no $2k(k-1)$-colouring and that is of girth at least $g$. By a seminal result of Erdős [25], such a graph $F$ exists (and its size is constant, as it only depends on $g$ and $k$ which are fixed integers). Notice that $F$ does not admit a vertex-partition into $k$ subgraphs with arboricity at most $k-1$, since otherwise $F$ would be $2k(k-1)$-colourable.

Now we consider the graph $S$ obtained by subdividing every edge of $F$ exactly once. The graph $S$ is 2-degenerate and bipartite with the old vertices from $F$ in one part and the new vertices of degree 2 in the other part. Moreover, $S$ has girth at least $g$, as $F$ has girth at least $g$.

We claim that $S$ has no acyclic $k$-colouring. For contradiction, assume that $S$ has an acyclic $k$-colouring. Assign the colour of every old vertex to the corresponding vertex of $F$ and assign the colour of every new vertex to the corresponding edge of $F$. For every colour $i$, we consider the subgraph $F_i$ of $F$ induced by the vertices coloured $i$. For every $j \ne i$, the subgraph of $S$ induced by the colours $i$ and $j$ is a forest. This implies that the subgraph of $F_i$ induces by the edges coloured $j$ is a forest. So the arboricity of $F_i$ is at most $k-1$, that is, the number of colours distinct from $i$. By previous discussion, the chromatic number of $F_i$ is at most $2(k-1)$, so that $F$ is $2k(k-1)$-colourable. This contradiction shows that $S$ has no acyclic $k$-colouring.

We repeatedly remove new vertices from $S$ until we obtain a graph $S'$ that is acyclically $k$-colourable. Note that $S'$ has girth at least $g$ and is 2-degenerate, as $S$ has girth at least $g$ and is 2-degenerate. Let $x_2$ be the last vertex that we removed and let $x_1$ and $x_3$ be the neighbours of $x_2$ in $S$. By construction, $S'$ is acyclically $k$-colourable and every acyclic $k$-colouring $c$ of $S'$ is such that:

* $c(x_1) = c(x_3)$, since otherwise setting $c(x_2) \notin \{c(x_1), c(x_3)\}$ would extend $c$ to an acyclic $k$-colouring of the larger graph, which is not possible by construction. Without loss of generality, $c(x_1) = c(x_3) = 1$.

* For every colour $i \ne 1$, $S'$ contains a bichromatic path coloured 1 and $i$ between $x_1$ and $x_3$, since otherwise setting $c(x_2) = i$ would extend $c$ to an acyclic $k$-colouring of the larger graph again.

We are ready to describe the reduction. Let $G$ be a bipartite instance of ACYCLIC $k$-COLOURING. We construct an equivalent instance $G'$ with girth at least $g$ as follows. For every vertex $z$ of $G$, we fix an arbitrary order on the neighbours of $z$. We replace $z$ of $G$ by $d$ vertices $z_1, z_2, \dots, z_d$, where $d$ is the degree of $z$. Then for $1 \le i \le d-1$, we take a copy of $S'$ and we identify the vertex $x_1$ of $S'$ with $z_i$ and the vertex $x_3$ of $S'$ with $z_{i+1}$. Now for every edge $uv$ of $G$, say $v$ is the $i^{th}$ neighbour of $u$ and $u$ is the $j^{th}$ neighbour of $v$, we add the edge $u_i v_j$ in $G'$. See also Fig. 1.

Given an acyclic $k$-colouring of $G$, we assign the colour of $z$ to $z_1, \dots, z_d$ and extend the colouring to the copies of $F'$, which gives an acyclic colouring of $G'$. Given an acyclic $k$-colouring of $G'$, the copies of $F'$ force the same colour on $z_1, \dots, z_d$ and we assign this common colour to $z$, which gives an acyclic $k$-colouring of $G$.

Finally, notice that since $G$ and $S'$ are bipartite, $G'$ is bipartite. As $S'$ is 2-degenerate and has girth at least $g$, we find that $G'$ is 2-degenerate and has girth at least $g$. □

The line graph of a graph $G$ has vertex set $E(G)$ and an edge between two vertices $e$ and $f$ if and only if $e$ and $f$ share an end-vertex of $G$. We now modify the construction of [5] for line graphs from $k=3$ to $k \ge 3$.

**Lemma 7.** For every $k \ge 3$, ACYCLIC $k$-COLOURING is NP-complete for line graphs of multigraphs.
<figure><img src="image_3.png" /><figcaption>**Fig. 1.** An example of part of a graph $G$ (left) and the corresponding part in $G'$ (right). In the part of $G'$ corresponding to vertex $u$, vertex $u_1$ is identified with $x_1$ of the left copy of $S'$; vertex $u_2$ with $x_3$ of the left copy of $S'$ and $x_1$ of the middle copy of $S'$; vertex $u_3$ with $x_3$ of the middle copy of $S'$ and $x_1$ of the right copy of $S'$; and $u_4$ with $x_3$ of the right copy of $S'$.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Fig. 2.** The gadget multigraph $F_k$. The labels on edges are multiplicities.</figcaption></figure>

**Proof.** For an integer $k \ge 1$, a *k-edge colouring* of a graph $G = (V, E)$ is a mapping $c : E \to \{1, \dots, k\}$ such that $c(e) \neq c(f)$ whenever the edges $e$ and $f$ share an end-vertex. A *colour class* consists of all edges of $G$ that are mapped by $c$ to a specific colour $i$. For a fixed integer $k \ge 1$, the *ACYCLIC k-EDGE COLOURING* problem is to decide if a given graph has an acyclic *k-edge colouring*. Alon and Zaks proved that *ACYCLIC 3-EDGE COLOURING* is NP-complete. We note that a graph has an acyclic *k-edge colouring* if and only if its line graph has an acyclic *k-colouring*. Hence, it remains to generalize the construction of Alon and Zaks [5] from $k=3$ to $k \ge 3$. Our main tool is the gadget graph $F_k$, depicted in Fig. 2, about which we prove the following two claims.

(i) The edges of $F_k$ can be coloured acyclically using $k$ colours, with no bichromatic path between $v_1$ and $v_{14}$.

(ii) Every acyclic *k-edge colouring* of $F_k$ using $k$ colours assigns $e_1$ and $e_2$ the same colour.

We first prove (ii). We assume, without loss of generality, that $v_1v_2$ is coloured by 1, $v_2v_4$ by 2 and the edges between $v_2$ and $v_3$ by colours 3, ..., $k$. The edge $v_3v_5$ has to be coloured by 1, otherwise we have a bichromatic cycle on $v_2v_3v_5v_4$. This necessarily implies that

* the edges between $v_4$ and $v_5$ are coloured by 3, ..., $k$,

* the edge $v_5v_7$ is coloured by 2,

* the edge $v_4v_6$ is coloured by 1,

* the edges between $v_6$ and $v_7$ are coloured by 3, ..., $k$, and

* the edge $v_7v_8$ is coloured by 1.

Now assume that the edge $v_8v_9$ is coloured by $a \in \{2, \dots, k\}$ and the edges between $v_8$ and $v_{10}$ by colours from the set $A$, where $A = \{2, \dots, k\} \setminus \{a\}$. The edge $v_{10}v_{11}$ is either coloured $a$ or 1. However, if it is coloured 1, $v_9v_{11}$ is assigned a colour $b \in A$ and necessarily we have either a bichromatic cycle on $v_8v_9v_{11}v_{13}v_{12}v_{10}$, coloured by $b$ and $a$, or a bichromatic cycle on $v_{10}v_{11}v_{13}v_{12}$, coloured by $a$ and 1. Thus $v_{10}v_{11}$ is coloured by $a$. To prevent a bichromatic cycle on $v_8v_9v_{11}v_{10}$, the edge $v_9v_{11}$ is assigned colour 1. The rest of the colouring is now determined as $v_{10}v_{12}$ has to be coloured by 1, the edges between $v_{11}$ and $v_{13}$ by $A$, $v_{12}v_{13}$ by $a$, and $v_{13}v_{14}$ by 1. We then have a *k-colouring* with no bichromatic cycles of size at least 3 in $F_k$ for every possible choice of $a$. This proves that $v_1v_2$ and $v_{13}v_{14}$ are coloured alike under every acyclic *k-edge colouring*.

We prove (i) by choosing $a$ different from 2. Then there is no bichromatic path between $v_1$ and $v_{14}$.

We now reduce from *k-EDGE-COLOURING* to *ACYCLIC k-EDGE COLOURING* as follows. Given an instance $G$ of $k$-EDGE COLOURING we construct an instance $G'$ of *ACYCLIC k-EDGE COLOURING* by replacing each edge $uv$ in $G$ by a copy of $F_k$ where $u$ is identified with $v_1$ and $v$ is identified with $v_{14}$.

If $G'$ has an acyclic *k-edge colouring* $c'$ then we obtain a *k-edge colouring* $c$ of $G$ by setting $c(uv) = c'(e_1)$ where $e_1$ belongs to the gadget $F_k$ corresponding to the edge $uv$. If $G$ has a *k-edge colouring* $c$ then we obtain an acyclic *k-edge colouring* $c'$.
colouring $c'$ of $G'$ by setting $c'(e_1) = c(uv)$ where $e_1$ belongs to the gadget corresponding to the edge $uv$. The remainder of each gadget $F_k$ can then be coloured as described above. $\square$

In our next result, $k$ is part of the input. Recall that a graph is co-bipartite if it is the complement of a bipartite graph. As bipartite graphs are $C_3$-free, co-bipartite graphs are $3P_1$-free.

**Lemma 8.** *ACYCLIC COLOURING is NP-complete for co-bipartite graphs.*

**Proof.** Alon et al. [3, Theorem 3.5] proved that deciding if a balanced bipartite graph on $2n$ vertices has a connected matching of size $n$ is NP-complete (the reduction in the proof of Theorem 3.5 in [3] works for every integer $k$, but in this proof, Theorem 3.1 from [3] must be replaced by Theorem 1.1 from [2].) A matching is called connected if no two edges of the matching induce $2K_2$ in the given graph. We shall reduce from this problem to prove our theorem.

To this end, we claim that a balanced bipartite graph $G$ with parts $A$ and $B$ such that $|A| = |B| = n$ has a connected matching of size $n$ if and only if its complement has an acyclic colouring with $n$ colours.

Suppose that there is an acyclic colouring $c$ of $\bar{G}$ with $n$ colours. Clearly, such colouring uses $n$ colours on $A$ and $n$ colours on $B$. Vertices coloured with the same colour do not have an edge between them in $\bar{G}$ and thus are connected by an edge in $G$. Let us take the set of edges formed by each of the $n$ colour classes. By the property of colouring, this is a matching in $G$ and it is of size $n$. To see that it is also connected, suppose for a contradiction that there are two edges of the matching, say $a_1b_1$ and $a_2b_2$, forming an induced $2K_2$ in $G$. Without loss of generality, $c(a_1) = c(b_1) = 1$ and $c(a_2) = c(b_2) = 2$. Now the induced $2K_2$ in $G$ corresponds to a 4-cycle in $\bar{G}$ coloured with two colours, a contradiction with $c$ being an acyclic colouring.

In the opposite direction, let us have a connected matching of size $n$ in $G$. Colour the $n$ vertices in $A$ by $1, \dots, n$. Let us colour the vertices of $B$ with respect to the connected matching so that each vertex of $B$ gets the colour of the vertex in $A$ it is matched to. Indeed, this is a colouring of $\bar{G}$ by $n$ colours. It remains to prove that it is acyclic. Any cycle in $G$ having more than five vertices has by the definition of our colouring at least three colours. Therefore, a possible bichromatic cycle in $\bar{G}$ must be of size 4. The only possibility for such 4-cycle is that it is formed by two pairs of vertices, each one forming an edge of the connected matching in $G$. However, this implies that these two matching edges induce $2K_2$ in $G$, a contradiction with the connectedness of the original matching. This finishes the proof our claim. $\square$

We combine the above results with a result of Lyons [56] to prove Theorem 1.

**Theorem 1 (restated).** Let $H$ be a graph. For the class of $H$-free graphs it holds that:

(i) *ACYCLIC COLOURING* is polynomial-time solvable if $H \subseteq P_4$ and NP-complete if $H \not\subseteq P_4$ and $H \neq 2P_2$;

(ii) *for every $k \ge 3$, ACYCLIC k-COLOURING* is polynomial-time solvable if $H$ is a linear forest and NP-complete otherwise.

**Proof.** We first prove (ii). First suppose that $H$ contains an induced cycle $C_p$. Then we use Lemma 6. Now assume $H$ has no cycle so $H$ is a forest. If $H$ has a vertex of degree at least 3, then $H$ has an induced $K_{1,3}$. As every line graph of a multigraph is $K_{1,3}$-free, we can use Lemma 7. Otherwise $H$ is a linear forest and we use Corollary 5.

We now prove (i). Due to (ii), we may assume that $H$ is a linear forest. If $H \subseteq P_4$, then we use the result of Lyons [56] that states that *ACYCLIC COLOURING* is polynomial-time solvable for $P_4$-free graphs. Now suppose $3P_1 \subseteq H$. By Lemma 8, *ACYCLIC COLOURING* is NP-complete for co-bipartite graphs and thus for $3P_1$-free graphs. It remains to consider the case where $H = 2P_2$, but this case was excluded from the statement of the theorem. $\square$

## 4. Star colouring

In this section we prove Theorem 2. We first prove the following lemma.

**Lemma 9.** *For every $g \ge 3$, STAR 3-COLOURING is NP-complete for planar graphs of girth at least $g$ and maximum degree 3.*

**Proof.** We reduce from 3-COLOURING, which is NP-complete even for planar graphs with maximum degree 4 [34]. Let $G$ be an instance of this restricted version of 3-COLOURING. The vertex gadget $V$ contains

* a cycle of length 12g with vertices $d_1, \dots, d_{12g}$,

* 12g independent vertices $e_1, \dots, e_{12g}$ such that $e_i$ is adjacent to $d_i$ for every $1 \le i \le 12g$, and

* four independent vertices $f_1, f_2, f_3, f_4$ such that $f_i$ is adjacent to $e_{3ig}$ for every $1 \le i \le 4$.

We construct an instance $G'$ of STAR 3-COLOURING from $G$ as follows. We consider a planar embedding of $G$ and for every vertex $x$, we order the neighbours of $x$ in a clockwise way. Then we replace $x$ by a copy $V_x$ of $V$. Now for every edge $mn$ of $G$, say $n$ is the $i^{th}$ neighbour of $m$ and $m$ is the $j^{th}$ neighbour of $n$, we add the edge between the vertex $f_i$ of $V_m$ and the vertex $f_j$ of $V_n$, see Fig. 3.
<figure><img src="image_5.png" /><figcaption>**Fig. 3.** A star 3-colouring of the graph $G'$ obtained from a 3-colouring of $G = K_3$. Only part of $G'$ is displayed.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Fig. 4.** The gadget $F_k$ in the proof of Lemma 11.</figcaption></figure>

It is not hard to check that in every star 3-colouring of $V$, the four vertices $f_i$ get the same colour. Moreover, there is no bichromatic path between any two vertices $f_i$.

Suppose that $G$ admits a 3-colouring $c$ of with colours in $\{0, 1, 2\}$. For every vertex $x$ in $G$, we assign $c(x)$ to the vertices $f_i$ in $V_x$ and we assign $(c(x)+1) \pmod 3$ to the vertices $e_{3ig}$. Then we extend this pre-colouring into a star 3-colouring of $V_x$. This gives a star 3-colouring of $G'$. Given a star 3-colouring of $G'$, we assign to every vertex $x$ in $G$ the colour of the vertices $f_i$ in $V_x$, which gives a 3-colouring of $G$.

Finally, as $G$ is planar with maximum degree 4, it holds that $G'$ is planar with maximum degree 3. Moreover, by construction, $G'$ has girth at least $g$. $\square$

Now we begin our development for Theorem 2.

**Lemma 10.** Let $p \ge 4$ be a fixed integer. Then, for every $k \ge 3$, STAR $k$-COLOURING is NP-complete for $C_p$-free graphs.

**Proof.** The case $k=3$ follows from Lemma 9. We obtain NP-completeness for $k \ge 4$ by a reduction from STAR 3-COLOURING for $C_p$-free graphs by adding a dominating clique of size $k-3$. $\square$

In Lemma 11 we extend the recent result of Lei et al. [51] from $k=3$ to $k \ge 3$.

**Lemma 11.** For every $k \ge 3$, STAR $k$-COLOURING is NP-complete for line graphs of multigraphs.

**Proof.** Recall that for an integer $k \ge 1$, a $k$-edge colouring of a graph $G = (V, E)$ is a mapping $c: E \rightarrow \{1, \dots, k\}$ such that $c(e) \neq c(f)$ whenever the edges $e$ and $f$ share an end-vertex. Recall also that the notions of a colour class and bichromatic subgraph for colourings have their natural analogue for edge colourings. A proper edge $k$-colouring $c$ is a star $k$-edge
colouring if the union of any two colour classes does not contain a path or cycle of on four edges. For a fixed integer $k \ge 1$, the STAR $k$-EDGE COLOURING problem is to decide if a given graph has a star $k$-edge colouring. Lei et al. [51] proved that STAR 3-EDGE COLOURING is NP-complete. Dvořák et al. [22] observed that a graph has a star $k$-edge colouring if and only if its line graph has a star $k$-colouring. Hence, it suffices to follow the proof of Lei et al. [51] in order to generalize the case $k=3$ to $k \ge 3$. As such, we give a reduction from $k$-EDGE COLOURING to STAR $k$-EDGE COLOURING which makes use of the gadget $F_k$ in Fig. 4. First we consider separately the case where the edges $e_1 = v_4v_9$ and $e_2 = v_5v_{10}$ are coloured alike and the case where they are coloured differently to show that in any star $k$-edge colouring of the gadget $F_k$ shown in Fig. 4, $v_1v_2$ and $v_7v_8$ are assigned the same colour.

Assume $c(e_1) = c(e_2) = 1$. We may then assume that the edge $v_4v_5$ is assigned colour 2 and the remaining $k-2$ colours are used for the multiple edges $v_3v_4$ and $v_5v_6$. The edge $v_2v_3$, and similarly $v_6v_7$, must then be assigned colour 1 to avoid a bichromatic $P_5$ on the vertices $\{v_2, v_3, v_4, v_5, v_6\}$ using any two of the multiple edges in a single colour. The edge $v_1v_2$, and similarly $v_7v_8$ must then be assigned colour 2 to avoid a bichromatic $P_5$ on the vertices $\{v_1, v_2, v_3, v_4, v_9\}$.

Next assume $e_1$ and $e_2$ are coloured differently. Without loss of generality, let $c(e_1) = 1$, $c(e_2) = 2$ and $c(v_4v_5) = 3$. The multiple edges $v_3v_4$ must then be assigned colours 2 and $4...k$ and $v_5v_6$ colour 1 and colours $4...k$. To avoid a bichromatic $P_5$ on the vertices $\{v_2, v_3, v_4, v_5, v_6\}$, $v_2v_3$ must be coloured 1. Similarly, $v_6v_7$ must be assigned colour 2. Finally, to avoid a bichromatic $P_5$ on the vertices $\{v_1, v_2, v_3, v_4, v_9\}$, $v_1v_2$ must be coloured 3. By a similar argument, $v_7v_8$ must also be coloured 3, hence $v_1v_2$ and $v_7v_8$ must be coloured alike.

We can then replace every edge $e$ in some instance $G$ of $k$-EDGE-COLOURING by a copy of $F_k$, identifying its endpoints with $v_1$ and $v_8$, to obtain an instance $G'$ of STAR $k$-EDGE-COLOURING. If $G$ is $k$-edge-colourable we can star $k$-edge-colour $G'$ by setting $c'(v_1v_2) = c'(v_7v_8) = c(e)$. If $G'$ is star $k$-edge-colourable, we obtain a $k$-edge-colouring of $G$ by setting $c(e) = c'(v_1v_2)$. $\square$

We now combine the above results with results of Albertson et al. [1], Lyons [56] and Shalu and Anthony [62] to prove Theorem 2.

**Theorem 2 (restated).** Let $H$ be a graph. For the class of $H$-free graphs it holds that:

(i) STAR COLOURING is polynomial-time solvable if $H \subseteq_i P_4$ and NP-complete if $H \not\subseteq_i P_4$ and $H \neq 2P_2$;

(ii) for every $k \ge 3$, STAR $k$-COLOURING is polynomial-time solvable if $H$ is a linear forest and NP-complete otherwise.

**Proof.** We first prove (ii). First suppose that $H$ contains an induced odd cycle. Then the class of bipartite graphs is contained in the class of $H$-free graphs. Lemma 7.1 in Albertson et al. [1] implies, together with the fact that for every $k \ge 3$, $k$-COLOURING is NP-complete, that for every $k \ge 3$, STAR $k$-COLOURING is NP-complete for bipartite graphs. If $H$ contains an induced even cycle, then we use Lemma 10. Now assume $H$ has no cycle, so $H$ is a forest. If $H$ contains a vertex of degree at least 3, then $H$ contains an induced $K_{1,3}$. As every line graph of a multigraph is $K_{1,3}$-free, we can use Lemma 11. Otherwise $H$ is a linear forest, in which case we use Corollary 5.

We now prove (i). Due to (ii), we may assume that $H$ is a linear forest. If $H \subseteq_i P_4$, then we use the result of Lyons [56] that states that STAR COLOURING is polynomial-time solvable for $P_4$-free graphs. Now suppose $3P_1 \subseteq_i H$. Shalu and Anthony [62] who proved that STAR COLOURING is NP-complete for co-bipartite graphs and thus for $3P_1$-free graphs. It remains to consider the case where $H = 2P_2$, but this case was excluded from the statement of the theorem. $\square$

## 5. Injective colouring

In this section we prove Theorem 3. We first show a hardness result for fixed $k$.<fnref n="4" />

**Lemma 12.** For every $k \ge 4$, INJECTIVE $k$-COLOURING is NP-complete for bipartite graphs.

**Proof.** We reduce from INJECTIVE $k$-COLOURING; recall that this problem is NP-complete for every $k \ge 4$. Let $G = (V, E)$ be a graph. We construct a graph $G'$ as follows. For each edge $uv$ of $G$, we remove the edge $uv$ and add two vertices $u'_v$, which we make adjacent to $u$, and $v'_u$, which we make adjacent to $v$. Next, we place an independent set $I_{uv}$ of $k-2$ vertices adjacent to both $u'_v$ and $v'_u$ (Fig. 5). Note that $G'$ is bipartite: we can let one partition class consist of all vertices of $V(G)$ and the vertices of the $I_{uv}$-sets and the other one consist of all the remaining vertices (that is, all the "prime" vertices we added). It remains to show that $G'$ has an injective $k$-colouring if and only if $G$ has an injective $k$-colouring.

First assume that $G$ has an injective $k$-colouring $c$. Colour the vertices of $G'$ corresponding to vertices of $G$ as they are coloured by $c$. We can extend this to an injective $k$-colouring $c'$ of $G'$ by considering the gadget corresponding to each edge $uv$ of $G$. Set $c'(u'_v) = c'(v)$ and $c'(v'_u) = c'(u)$. We can now assign the remaining $k-2$ colours to the vertices of the independent sets. Clearly $c'$ creates no bichromatic $P_3$ involving vertices in at most one edge gadget. Assume there exists

<footnote n="4">⁴ We note that Janczewski et al. [42] proved that L(p, q)-LABELLING is NP-complete for planar bipartite graphs, but in their paper they assumed that $p > q$.</footnote>
<figure><img src="image_7.png" /><figcaption>Fig. 5. The edge gadget used in the proof of Lemma 12.</figcaption></figure>

a bichromatic $P_3$ involving vertices in more than one edge gadget, then this path must consist of a vertex $u$ of $G$ together with two gadget vertices $u'_v$ and $u'_w$ which are coloured alike. This is a contradiction since it implies the existence of a bichromatic path $v, u, w$ in $G$.

Now assume that $G'$ has an injective $k$-colouring $c'$. Let $c$ be the restriction of $c'$ to those vertices of $G'$ which correspond to vertices of $G$. To see that $c$ is an injective colouring of $G$, note that we must have $c'(u'_v) = c'(v)$ and $c'(v'_u) = c'(u)$ for any edge $uv$. Therefore, if $c$ induces a bichromatic $P_3$ on $u, v, w$, then $c'$ induces a bichromatic $P_3$ on $v'_u, v, v'_w$. We conclude that $c$ is injective. $\square$

We now turn to the case where $k$ is part of the input and first prove a number of positive results. The complement of a graph $G$ is the graph $\bar{G}$ with vertex set $V(G)$ and an edge between two vertices $u$ and $v$ if and only if $uv \notin E(G)$. An injective colouring $c$ of a graph $G$ is optimal if $G$ has no injective colouring using fewer colours than $c$. An injective colouring $c$ is $\ell$-injective if every colour class of $c$ has size at most $\ell$. An $\ell$-injective colouring $c$ of a graph $G$ is $\ell$-optimal if $G$ has no $\ell$-injective colouring that uses fewer colours than $c$. We start with a useful lemma for the case where $\ell = 2$ that we will also use in our proofs.

**Lemma 13.** *An optimal 2-injective colouring of a graph *G* can be found in polynomial time.*

**Proof.** Let $c$ be a 2-injective colouring of $G$. Then each colour class of size 2 in $G$ corresponds to a dominating edge of $\bar{G}$ (an edge $uv$ of a graph is dominating if every other vertex in the graph is adjacent to at least one of $u, v$). Hence, the end-vertices of every non-dominating edge in $\bar{G}$ have different colours in $G$. Algorithmically, this means we may delete every non-dominating edge of $\bar{G}$ from $\bar{G}$; note that we do not delete the end-vertices of such an edge.

Let $\mu^*$ be the size of a maximum matching in the graph obtained from $\bar{G}$ after deleting all non-dominating edges of $\bar{G}$. The edges in such a matching will form exactly the colour classes of size 2 of an optimal 2-injective colouring of $G$. Hence, the injective chromatic number of $G$ is equal to $\mu^* + (|V(G)| - 2\mu^*)$. It remains to observe that we can find a maximum matching in a graph in polynomial time by using a standard algorithm. $\square$

We can now prove our first positive result.

**Lemma 14.** *INJECTIVE COLOURING is polynomial-time solvable for (P<sub>1</sub> + P<sub>4</sub>)-free graphs.*

**Proof.** Let $G$ be a $(P_1 + P_4)$-free graph. Since connected $P_4$-free graphs have diameter at most 2, no two vertices can be coloured alike in an injective colouring. Hence, the injective chromatic number of a $P_4$-free graph is equal to the number of its vertices. Consequently, INJECTIVE COLOURING is polynomial-time solvable for $P_4$-free graphs. From now on, we assume that $G$ is not $P_4$-free.

We first show that any colour class in any injective colouring of $G$ has size at most 2. For contradiction, assume that $c$ is an injective colouring of $G$ such that there exists some colour, say colour 1, that has a colour class of size at least 3. Let $P = x_1x_2x_3x_4$ be some induced $P_4$ of $G$.

We first consider the case where colour 1 appears at least twice on $P$. As no vertex has two neighbours coloured with the same colour, the only way in which this can happen is when $c(x_1) = c(x_4) = 1$. By our assumption, $G - P$ contains a vertex $u$ with $c(u) = 1$. As $G$ is $(P_1 + P_4)$-free, $u$ has a neighbour on $P$. As every colour class is an independent set, this means that $u$ must be adjacent to at least one of $x_2$ and $x_3$. Consequently, either $x_2$ or $x_3$ has two neighbours with colour 1, a contradiction.

Now we consider the case where colour 1 appears exactly once on $P$, say $c(x_h) = 1$ for some $h \in \{1, 2, 3, 4\}$. Then, by our assumption, $G - P$ contains two vertices $u_1$ and $u_2$ with colour 1. As $G$ is $(P_1 + P_4)$-free, both $u_1$ and $u_2$ must be adjacent to at least one vertex of $P$, say $u_1$ is adjacent to $x_i$ and $u_2$ is adjacent to $x_j$. Then $x_i \neq x_j$, as otherwise $G$ has a vertex with two neighbours coloured 1. As every colour class is an independent set, we have that $x_h \notin \{x_i, x_j\}$, and hence, $x_h, x_i, x_j$ are distinct vertices. Moreover, $x_h$ is not a neighbour of $x_i$ or $x_j$, as otherwise $x_i$ or $x_j$ has two neighbours coloured 1. Hence, we may assume without loss of generality that $h = 1$, $i = 3$ and $j = 4$. As every colour class is an independent set, $u_1$ and $u_2$ are non-adjacent. However, now $\{x_1, u_1, x_3, x_4, u_2\}$ induces a $P_1 + P_4$, a contradiction.

Finally, we consider the case where colour 1 does not appear on $P$. Let $u_1, u_2, u_3$ be three vertices of $G - P$ coloured 1. As before, $\{u_1, u_2, u_3\}$ is an independent set and each $u_i$ has a different neighbour on $P$. We first consider the case where
<figure><img src="image_8.png" /><figcaption>**Fig. 6.** The partition of $V(G)$ from Lemma 15. The squares inside each $T_i$, $i \in \{1, 2, 3\}$, represent the sets of 0-clique-adjacent, 1-clique-adjacent and 2-clique-adjacent vertices in $T_i$, respectively.</figcaption></figure>

$x_1$ or $x_4$, say $x_4$ is not adjacent to any $u_i$. Then we may assume without loss of generality that $u_1x_1$ and $u_2x_2$ are edges. However, now $\{x_4, u_1, x_1, x_2, u_2\}$ induces a $P_1 + P_4$, which is not possible. Hence, we may assume without loss of generality that $u_1x_1, u_2x_2$ and $u_4x_4$ are edges of $G$. Again we find that $\{x_4, u_1, x_1, x_2, u_2\}$ induces a $P_1 + P_4$, a contradiction.

From the above, we find that each colour class in an injective colouring of $G$ has size at most 2. This means we can use Lemma 13. □

We use the next lemma in the proofs of the results for $H = 2P_1 + P_3$ and $H = 3P_1 + P_2$.

**Lemma 15.** *INJECTIVE COLOURING is polynomial-time solvable for $4P_1$-free graphs.*

**Proof.** Let $G = (V, E)$ be a $4P_1$-free graph on $n$ vertices. We first analyze the structure of injective colourings of $G$. Let $c$ be an optimal injective colouring of $G$. As $G$ is $4P_1$-free, every colour class of $c$ has size at most 3. From all optimal injective colourings, we choose $c$ such that the number of size-3 colour classes is as small as possible. We say that $c$ is class-3-optimal.

Suppose $c$ contains a colour class of size 3, say colour 1 appears on three distinct vertices $u_1, u_2$ and $u_3$ of $G$. As $G$ is $4P_1$-free, $\{u_1, u_2, u_3\}$ dominates $G$. As $c$ is injective, this means that every vertex in $G - \{u_1, u_2, u_3\}$ is adjacent to exactly one vertex of $\{u_1, u_2, u_3\}$. Hence, we can partition $V - \{u_1, u_2, u_3\}$ into three sets $T_1, T_2$ and $T_3$, such that for $i \in \{1, 2, 3\}$, every vertex of $T_i$ is adjacent to $u_i$ and not to any other vertex of $\{u_1, u_2, u_3\}$. If two vertices $t, t'$ in the same $T_i$, say $T_1$, are non-adjacent, then $\{t, t', u_2, u_3\}$ induces a $4P_1$, a contradiction. Hence, we partitioned $V$ into three cliques $T_i \cup \{u_i\}$. We call the cliques $T_1, T_2, T_3$, the T-cliques of the triple $\{u_1, u_2, u_3\}$.

Let $t \in T_i$ for some $i \in \{1, 2, 3\}$. For $i \in \{0, 1, 2\}$ we say that $t$ is i-clique-adjacent if $t$ has a neighbour in zero, one or two cliques of $\{T_1, T_2, T_3\} \setminus T_i$, respectively. By the definition of an injective colouring and the fact that every $T_i$ is a clique, a 1-clique-adjacent vertex of $T_1 \cup T_2 \cup T_3$ belongs to a colour class of size at most 2, and a 2-clique-adjacent vertex of $T_1 \cup T_2 \cup T_3$ belongs to a colour class of size 1. Hence, all the vertices that belong to a colour class of size 3 are 0-clique-adjacent. The partition of $V(G)$ is illustrated in Fig. 6.

We now use the fact that $c$ is class-3-optimal. Let $t \in V - \{u_1, u_2, u_3\}$, say $t \in T_1$, be i-clique-adjacent for $i=0$ or $i=1$. Then we may assume without loss of generality that $t$ has no neighbours in $T_2$. If $t$ belongs to a colour class of size 1, then we can set $c(u_2) := c(t)$ to obtain an optimal injective colouring with fewer size-3 colour classes, contradicting our choice of $c$.

We now consider the 0-clique-adjacent vertices again. Recall that these are the only vertices, other than $u_1, u_2$ and $u_3$, that may belong to a colour class of size 3. As every $T_i$ is a clique, every colour class of size 3 (other than $\{u_1, u_2, u_3\}$) has exactly one vertex of each $T_i$. Let $\{w_1, w_2, w_3\}$ be another colour class of size 3 with $w_i \in T_i$ for every $i \in \{1, 2, 3\}$. Let $x \in T_1 - \{w_1\}$ be another 0-clique-adjacent vertex. Then swapping the colours of $w_1$ and $x$ yields another class-3-optimal injective colouring of $G$. Hence, we derived the following claim, which summarizes the discussion above and where statement (iv) follows from (i)-(iii).

**Claim.** Let $c$ be a class-3-optimal injective colouring of $G$ with $c(u_1) = c(u_2) = c(u_3)$ for three distinct vertices $u_1, u_2, u_3$ and with $p \ge 0$ other colour classes of size 3. Then the following four statements hold:

(i) All 0-clique-adjacent and 1-clique-adjacent vertices belong to a colour class of size at least 2.

(ii) Let $S = \{y_1, \dots, y_s\}$ be the set of 2-clique-adjacent vertices. Then $\{y_1\}, \dots, \{y_s\}$ are exactly the size-1 colour classes.

(iii) For $i \in \{1, 2, 3\}$, let $x_i^1, \dots, x_{q_i}^1$ be the 0-clique-adjacent vertices of $T_i$ and assume without loss of generality that $q_1 \le q_2 \le q_3$. Then $p \le q_1$ and if $p \ge 1$, we may assume without loss of generality that the size-3 classes, other than $\{u_1, u_2, u_3\}$, are $\{x_1^1, x_1^2, x_1^3\}, \dots, \{x_p^1, x_p^2, x_p^3\}$.

(iv) The number of colours used by $c$, or equivalently, the number of colour classes of $c$ is equal to $1 + s + p + \frac{1}{2}(n - s - 3(p+1)) = \frac{1}{2}n + \frac{1}{2}s - \frac{1}{2}p - \frac{1}{2}$.

We are now ready to present our algorithm. We first find, in polynomial time, an optimal 2-injective colouring of $G$ by Lemma 13. We remember the number of colours used. Recall that the colour classes of every injective colouring of $G$ have size at most 3. So, it remains to compute an optimal injective colouring for which at least one colour class has size 3.
We consider each triple $u_1, u_2, u_3$ of vertices of G and check if $\{u_1, u_2, u_3\}$ can be a colour class. That is, we check if $\{u_1, u_2, u_3\}$ is an independent set and has corresponding $T$-cliques $T_1, T_2, T_3$. This takes polynomial time. If not, then we discard $\{u_1, u_2, u_3\}$. Otherwise we continue as follows. Let $S = \{y_1, \dots, y_s\}$ be the set of 2-clique adjacent vertices in $T_1 \cup T_2 \cup T_3$. Exactly the vertices of $S$ will form the size-1 colour classes by Claim (ii). For $i \in \{1, 2, 3\}$, let $x_i^1, \dots, x_{q_i}^i$ be the 0-clique-adjacent vertices of $T_i$, where we assume without loss of generality that $q_1 \le q_2 \le q_3$. By Claim (iii), any injective colouring of G which has $\{u_1, u_2, u_3\}$ as one of its colour classes has at most $q_1$ other colour classes of size 3 besides $\{u_1, u_2, u_3\}$. As can be seen from Claim (iv), the value $\frac{1}{2}n + \frac{1}{2}s - \frac{1}{2}p - \frac{1}{2}$ is minimized if the number $p$ of size-3 colour classes is maximum.

From the above we can now do as follows. For $p = q_1, \dots, 1$, we check if G has an injective colouring with exactly $p$ colour classes of size 3. We stop as soon as we find a yes-answer or if $p$ is set to 0. We first set $\{x_1^1, x_1^2, x_1^3\}, \dots, \{x_p^1, x_p^2, x_p^3\}$ as the colour classes of size 3 by Claim (iii). Let $Z$ be the set of remaining 0-clique-adjacent and 1-clique-adjacent vertices. We use Lemma 13 to check in polynomial time if the subgraph of G induced by $S \cup Z$ has an injective colouring that uses $s + \frac{1}{2}(n - s - 3(p+1))$ colours (which is the minimum number of colours possible). If so, then we stop and note that after adding the size-3 colour classes we obtained an injective colouring of G that uses $\frac{1}{2}n + \frac{1}{2}s - \frac{1}{2}p - \frac{1}{2}$ colours, which we remember. Otherwise we repeat this step after first setting $p := p-1$.

As the above procedure for a triple $u_1, u_2, u_3$ takes polynomial time and the number of triples we must check is $O(n^3)$, our algorithm runs in polynomial time. We take the 3-injective colouring that uses the smallest number of colours and compare it with the number of colours used by the optimal 2-injective colouring that we computed at the start. Our algorithm then returns a colouring with the smallest of these two values as its output. $\square$

We use the above lemma for proving our next lemma.

**Lemma 16.** INJECTIVE COLOURING is polynomial-time solvable for $(2P_1 + P_3)$-free graphs.

**Proof.** Let $G = (V, E)$ be a $(2P_1 + P_3)$-free graph. We may assume without loss of generality that $G$ is connected and by Lemma 15 that $G$ has an induced $4P_1$. We first show that any colour class in any injective colouring of $G$ has size at most 2. For contradiction, assume that $c$ is an injective colouring of $G$ such that there exists some colour, say colour 1, that has a colour class of size at least 3. Let $U = \{u_1, \dots, u_p\}$ for some $p \ge 3$ be the set of vertices of $G$ with $c(u_i) = 1$ for $i \in \{1, \dots, p\}$.

As $c$ is injective, every vertex in $G - U$ has at most one neighbour in $U$. Hence, we can partition $G - U$ into (possibly empty) sets $T_0, \dots, T_p$, where $T_0$ is the set of vertices with no neighbour in $U$ and for $i \in \{1, \dots, p\}$, $T_i$ is the set of vertices of $G - U$ adjacent to $u_i$.

We first claim that $T_0$ is empty. For contradiction, assume $v \in T_0$. As $G$ is connected, we may assume without loss of generality that $v$ is adjacent to some vertex $t \in T_1$. Then $\{u_2, u_3, u_1, t, v\}$ induces a $2P_1 + P_3$, a contradiction. Hence, $T_0 = \emptyset$.

We now prove that every $T_i$ is a clique. For contradiction, assume that $t$ and $t'$ are non-adjacent vertices of $T_1$. Then $\{u_2, u_3, t, u_1, t'\}$ induces a $2P_1 + P_3$, a contradiction. Hence, every $T_i$ and thus every $T_i \cup \{u_i\}$ is a clique.

We now claim that $p=3$. For contradiction, assume that $p \ge 4$. As $G$ is connected and $U$ is an independent set, we may assume without of generality that there exist vertices $t_1 \in T_1$ and $t_2 \in T_2$ with $t_1 t_2 \in E$. Then $\{u_3, u_4, u_1, t_1, t_2\}$ induces a $2P_1 + P_3$, a contradiction. Hence, $p=3$.

Now we know that $V$ can be partitioned into three cliques $T_1 \cup \{u_1\}, T_2 \cup \{u_2\}$ and $T_3 \cup \{u_3\}$. However, then $G$ is $4P_1$-free, a contradiction. We conclude that every colour class of every injective colouring of $G$ has size at most 2. This means we can use Lemma 13. $\square$

We also use Lemma 15 in the proof of our next result.

**Lemma 17.** INJECTIVE COLOURING is polynomial-time solvable for $(3P_1 + P_2)$-free graphs.

**Proof.** Let $G$ be a $(3P_1 + P_2)$-free graph on $n$ vertices. We may assume without loss of generality that $G$ is connected and by Lemma 15 that $G$ has an induced $4P_1$. As before, we will first analyze the structure of injective colourings of $G$. We will then exploit the properties found algorithmically.

Let $c$ be an injective colouring of $G$ that has a colour class $U$ of size at least 3. So let $U = \{u_1, \dots, u_p\}$ for some $p \ge 3$ be the set of vertices of $G$ with, say colour 1. As $c$ is injective, every vertex in $G - U$ has at most one neighbour in $U$. Hence, we can partition $G - U$ into (possibly empty) sets $T_0, \dots, T_p$, where $T_0$ is the set of vertices with no neighbour in $U$ and for $i \in \{1, \dots, p\}$, $T_i$ is the set of vertices of $G - U$ adjacent to $u_i$.

Assume that $p \ge 4$. As $G$ is connected, there exists a vertex $v \notin U$ but that has a neighbour in $U$, say $v \in T_1$. Then $\{u_2, u_3, u_4, u_1, v\}$ induces a $3P_1 + P_2$, a contradiction. Hence, we have shown the following claim.

*Claim 1.* Every injective colouring of $G$ is $\ell$-injective for some $\ell \in \{1, 2, 3\}$.

We continue as follows. As $p=3$ by Claim 1, we have $V(G) = U \cup T_0 \cup T_1 \cup T_2 \cup T_3$. Suppose $T_0$ contains two adjacent vertices $x$ and $y$. Then $\{u_1, u_2, u_3, x, y\}$ induces a $3P_1 + P_2$, a contradiction. Hence, $T_0$ is an independent set. As $G$ is connected, this means each vertex in $T_0$ has a neighbour in $T_1 \cup T_2 \cup T_3$.
<figure><img src="image_9.png" /><figcaption>**Fig. 8.** The graph $G'$ constructed in the proof of Lemma 19.</figcaption></figure>

returns the minimum of the two values as the output. Since both colourings are found in polynomial time, we conclude that our algorithm runs in polynomial time. □

For proving our new hardness result we first need to introduce some terminology and prove a lemma on COLOURING. A k-colouring of G can be seen as a partition of V(G) into k independent sets. Hence, a (k-)colouring of G corresponds to a (k-)clique-covering of $\bar{G}$, which is a partition of $V(\bar{G}) = V(G)$ into k cliques. The clique covering number $\bar{\chi}(G)$ of G is the smallest number of cliques in a clique-covering of G. Note that $\bar{\chi}(G) = \chi(\bar{G})$.

**Lemma 18.** COLOURING is NP-complete for graphs with $\bar{\chi} \le 3$.

**Proof.** The LIST COLOURING problem takes as input a graph G and a list assignment L that assigns each vertex $u \in V(G)$ a list $L(u) \subseteq \{1, 2, \dots\}$. The question is whether G admits a colouring c with $c(u) \in L(u)$ for every $u \in V(G)$. Jansen [43] proved that LIST COLOURING is NP-complete for co-bipartite graphs. This is the problem we reduce from.

Let G be a graph with a list assignment L and assume that V(G) can be split into two (not necessarily disjoint) cliques K and K'. We set $A_1 := K$ and $A_2 := K \setminus K'$. As both $A_1$ and $A_2$ are cliques, we have that $\bar{\chi}(G) \le 2$. We may assume without loss of generality that the union of all the lists $L(u)$ is $\{1, \dots, k\}$ for some integer k. We now extend G by adding a clique $A_3$ of k new vertices $v_1, \dots, v_k$ and by adding an edge between a vertex $v_\ell$ and a vertex $u \in V(G)$ if and only if $\ell \notin L(u)$. This yields a new graph $G'$ with $\bar{\chi}(G') \le 3$. It is readily seen that G has a colouring c with $c(u) \in L(u)$ for every $u \in V(G)$ if and only if $G'$ has a k-colouring. □

We use Lemma 18 to prove the next lemma.

**Lemma 19.** INJECTIVE COLOURING is NP-complete for 5$P_1$-free graphs.

**Proof.** The problem is readily seen to belong to NP. We reduce from COLOURING. Let $(G, k)$ be an instance of this problem. By Lemma 18 we may assume that $V(G)$ can be partitioned into three cliques $A_1, A_2$ and $A_3$ with $|A_1| \le |A_2| \le |A_3|$. We may assume that $k \ge |A_3|$; otherwise $(G, k)$ is a no-instance. Moreover, we may assume that every vertex $u$ in every $A_i$ has at least one neighbour in $V \setminus A_i$; otherwise $u$ has degree $|A_i| - 1 \le k - 1$ and hence, $G - u$ is k-colourable if and only if G is k-colourable.

We now construct a graph $G'$ as follows. Let $E^*$ be the set of edges in G whose end-vertices belong to different cliques of $\{A_1, A_2, A_3\}$. We add a clique $A_0$ of $|E^*|$ new vertices, so with exactly one vertex $v_e$ for each edge $e = xy$ in $E^*$. We replace each $e \in E^*$ by the edges $xv_e$ and $yv_e$. We denote the resulting graph by $G'$ (see also Fig. 8). We claim that G has a k-colouring if and only if $G'$ has an injective $(k + |E^*|)$-colouring.

First suppose that G has a k-colouring c. We give each vertex of $A_0$ a unique colour from $\{k+1, \dots, k+|E^*|\}$. This yields a $(k + |E^*|)$-colouring $c'$ of $G'$. We claim that $c'$ is injective. In order to see this, suppose that $G'$ contains a vertex s that has two neighbours x and y with $c'(x) = c'(y)$. Every vertex in $A_1 \cup A_2 \cup A_3$ is only adjacent to vertices from its own clique $A_i$ and $A_0$ and the colour sets used on those two cliques do not intersect. Hence, s belongs to $A_0$. Then, by definition of $G'$, we find that x and y must belong to different cliques $A_h$ and $A_i$. By construction, xy is an edge in E. As c is a k-colouring, this means that $c'(x) = c(x) \ne c(y) = c'(y)$, a contradiction. We conclude that $c'$ is an injective $(k + |E^*|)$-colouring of $G'$.

Now suppose that $G'$ has a $(k + |E^*|)$-colouring $c'$. Let $e \in A_0$ and suppose $c'(e) = 1$. We assume without loss of generality that $e$ corresponds to an edge $e = xy$ in G with $x \in A_1$ and $y \in A_2$. Then, in $G'$, we have that $e$ is adjacent to x and to y. Hence, x and y are not coloured 1. As $c'$ is injective, the neighbours of x and y have different colours. As $A_1$ and $A_2$ are cliques, x is adjacent to every vertex in $A_1 \setminus \{x\}$ and y is adjacent to every vertex in $A_2 \setminus \{y\}$. Hence, no vertex in $A_1 \cup A_2$ can have colour 1.

Now suppose that there exists a vertex $z \in A_3$ with $c'(z) = 1$. In G each vertex in every $A_i$ has at least one neighbour in a different clique $A_j$. Hence, z has a neighbour $f \in A_0$ in $G'$ by construction of $G'$. However, now f has two neighbours, e and z, each with colour 1, contradicting the fact that $c'$ is injective. We conclude that the colours of $A_0$ do not occur on $A_1 \cup A_2 \cup A_3$.
Recall that $A_0$ is a clique of size $|E^*|$. Hence, $c'$ uses $|E^*|$ different colours. As no colour of $A_0$ occurs on $A_1 \cup A_2 \cup A_3$, this means that $|E^*|$ colours are not used on $V(G)$. Hence, the restriction $c$ of $c'$ to $V(G) = A_1 \cup A_2 \cup A_3$ is a $k$-colouring of the subgraph of $G'$ induced by $A_1 \cup A_2 \cup A_3$.

We claim that $c$ is even a $k$-colouring of $G$. Otherwise, if there exists an edge $e = xy$ with $c(x) = c(y)$, then $e$ must be an edge in $G$ that is not in $G'$. This means that $x$ and $y$ must belong to different cliques $A_i$ and $A_j$. By construction, $G'$ then contains the vertex $e = xy$. However, then $c'(x) = c(x) = c(y) = c(y')$ and $e'$ has two neighbours with the same colour. This contradicts our assumption that $c'$ is injective. We conclude that $c$ is a $k$-colouring of $G$. □

We combine the above results with results of Bodlaender et al. [9] and Mahdian [58] to prove Theorem 3.

**Theorem 3 (restated).** Let $H$ be a graph. For the class of $H$-free graphs it holds that:

(i) INJECTIVE COLOURING is polynomial-time solvable if $H \subseteq_i 2P_1 + P_4$ and NP-complete if $H \not\subseteq_i 2P_1 + P_4$;

(ii) for every $k \ge 4$, INJECTIVE $k$-COLOURING is polynomial-time solvable if $H$ is a linear forest and NP-complete otherwise.

**Proof.** We first prove (ii). If $C_3 \subseteq_i H$, then we use Lemma 12. Now suppose $C_p \subseteq_i H$ for some $p \ge 4$. Mahdian [58] proved that for every $g \ge 4$ and $k \ge 4$, INJECTIVE $k$-COLOURING is NP-complete for line graphs of bipartite graphs of girth at least $g$. These graphs may not be $C_3$-free but are $C_p$-free for $g \ge p+1$. Now assume $H$ has no cycle, so $H$ is a forest. If $H$ contains a vertex of degree at least 3, then $H$ contains an induced $K_{1.3}$. As every line graph is $K_{1.3}$-free, we can use the aforementioned result of Mahdian [58] again. Otherwise $H$ is a linear forest, in which case we use Corollary 5.

We now prove (i). Due to (ii), we may assume that $H$ is a linear forest. If $H \subseteq_i P_1 + P_4$ or $H \subseteq_i 2P_1 + P_3$ or $H \subseteq_i 3P_1 + P_2$, then we use Lemma 14, 16, or 17, respectively. Hence, if $H \subseteq_i 2P_1 + P_4$, then INJECTIVE COLOURING is polynomial-time solvable for $H$-free graphs. Now suppose that $H \not\subseteq_i 2P_1 + P_4$. If $2P_2 \subseteq_i H$, then the class of $(2P_2, C_4, C_5)$-free graphs are contained in the class of $H$-free graphs. The latter class coincides with the class of split graphs [27]. Recall that Bodlaender et al. [9] proved that INJECTIVE COLOURING is NP-complete for split graphs. In the remaining case it holds that $5P_1 \subseteq_i H$, and for this case we can use Lemma 19. □

# 6. Conclusions

Our complexity study led to three complete and three almost complete complexity classifications (Theorems 1–3). Due to our systematic approach we were able to identify a number of open questions for future research, which we collect below.

In Lemma 6 we prove that for every $k \ge 3$ and every $g \ge 3$, ACYCLIC $k$-COLOURING is NP-complete for graphs of girth at least $g$. We would like to prove an analogous result for the third problem we considered. We recall that INJECTIVE 3-COLOURING is polynomial-time solvable for general graphs. Moreover, for every $k \ge 4$, INJECTIVE $k$-COLOURING is NP-complete for bipartite graphs (by Lemma 12) and thus for graphs of girth at least 4. Hence, we pose the following open problem.

**Open Problem 1.** For every $g \ge 5$, determine the complexity of INJECTIVE COLOURING and INJECTIVE $k$-COLOURING ($k \ge 4$) for graphs of girth at least $g$.

This problem has eluded us and remains open and is, we believe, challenging. We note that recently it was shown that INJECTIVE 4-COLOURING is NP-complete for planar subcubic graphs of girth 11 [50], which improves upon a previous bound of 9 [23].

We have made progress for the corresponding high-girth problem for STAR 3-COLOURING in Lemma 9. However, we leave the high-girth problem for STAR $k$-COLOURING open for $k \ge 4$, as follows. We believe it represents an interesting technical challenge. At the moment, we only know that for $k \ge 4$, STAR $k$-COLOURING is NP-complete for bipartite graphs [1] and thus for graphs of girth at least 4.

**Open Problem 2.** For every $g \ge 5$, determine the complexity of STAR $k$-COLOURING ($k \ge 4$) for graphs of girth at least $g$.

Naturally we also aim to settle the remaining open cases for our three problems in Table 1. In particular, there is one case left for each of the problems ACYCLIC COLOURING, STAR COLOURING, and INJECTIVE COLOURING. We note that the graph $G'$ in the proof of Lemma 19 contains an induced $2P_1 + P_4$.

**Open Problem 3.** Determine the complexity of INJECTIVE COLOURING for $(2P_1 + P_4)$-free graphs.

**Open Problem 4.** Determine the complexity of ACYCLIC COLOURING and STAR COLOURING for $2P_2$-free graphs.

Recall that INJECTIVE COLOURING and COLOURING are NP-complete for $2P_2$-free graphs. However, none of the hardness constructions for these problems carry over to ACYCLIC COLOURING and STAR COLOURING. In this context, the next open problem from Lyons [57] for a subclass of $2P_2$-free graphs is also interesting. A graph $G = (V, E)$ is split if $V = I \cup K$, where $I$
is an independent set, $K$ is a clique and $I \cap K = \emptyset$. The class of split graphs coincides with the class of $(2P_2, C_4, C_5)$-free graphs [27] and thus ACYCLIC COLOURING is equivalent to COLOURING for split graphs, and hence it is polynomial-time solvable. However, for STAR COLOURING this equivalence is no longer true.

**Open Problem 5** ([57]). Determine the complexity of STAR COLOURING for split graphs, or equivalently, $(2P_2, C_4, C_5)$-free graphs.

Let $\omega(G)$ denote the clique number of $G$ (size of a largest clique of $G$). Let $\chi_s(G)$ denote the star chromatic number of $G$. It is easily observed (see also [57]) that if $G$ is a split graph, then either $\chi_s(G) = \omega(G)$ or $\chi_s(G) = \omega(G) + 1$.

Finally, we recall that INJECTIVE COLOURING is also known as $L(1, 1)$-labelling. The general distance constrained labelling problem $L(a_1, \dots, a_p)$-LABELLING is to decide if a graph $G$ has a labelling $c: V(G) \to \{1, \dots, k\}$ for some integer $k \ge 1$ such that for every $i \in \{1, \dots, p\}$, $|c(u) - c(v)| \ge a_i$ whenever $u$ and $v$ are two vertices of distance $i$ in $G$ (in this setting, it is usually assumed that $a_1 \ge \dots \ge a_p$). If $k$ is fixed, we write $L(a_1, \dots, a_p)$-$k$-LABELLING instead. By applying Theorem 4 we obtain the following result.

**Theorem 20.** For all $k \ge 1$, $a_1 \ge 1, \dots, a_k \ge 1$, the $L(a_1, \dots, a_p)$-$k$-LABELLING problem is polynomial-time solvable for $H$-free graphs if $H$ is a linear forest.

We leave a more detailed and systematic complexity study of problems in this framework for future work (see, for example, [16,31,32] for some complexity results for both general graphs and special graph classes).

**CRediT authorship contribution statement**

**Jan Bok:** Conceptualization, Data curation, Formal analysis, Funding acquisition, Investigation, Methodology, Project administration, Resources, Supervision, Validation, Visualization, Writing – original draft, Writing – review & editing. **Nikola Jedličková:** Conceptualization, Data curation, Formal analysis, Funding acquisition, Investigation, Methodology, Project administration, Resources, Supervision, Validation, Visualization, Writing – original draft, Writing – review & editing. **Barnaby Martin:** Conceptualization, Data curation, Formal analysis, Funding acquisition, Investigation, Methodology, Project administration, Resources, Supervision, Validation, Visualization, Writing – original draft, Writing – review & editing. **Pascal Ochem:** Conceptualization, Data curation, Formal analysis, Funding acquisition, Investigation, Methodology, Project administration, Resources, Supervision, Validation, Visualization, Writing – original draft, Writing – review & editing. **Daniël Paulusma:** Conceptualization, Data curation, Formal analysis, Funding acquisition, Investigation, Methodology, Project administration, Resources, Supervision, Validation, Visualization, Writing – original draft, Writing – review & editing. **Siani Smith:** Conceptualization, Data curation, Formal analysis, Funding acquisition, Investigation, Methodology, Project administration, Resources, Supervision, Validation, Visualization, Writing – original draft, Writing – review & editing.

**Declaration of competing interest**

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

**Acknowledgments**

We thank Cyriac Antony for helpful comments.

**Data availability**

No data was used for the research described in the article.

**References**

[1] Michael O. Albertson, Glenn G. Chappell, Henry A. Kierstead, André Kündgen, Radhika Ramamurthi, Coloring with no 2-colored $P_4$'s, Electron. J. Comb. 11 (2004).

[2] Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, Erratum: multitasking capacity: hardness results and improved constructions, SIAM J. Discrete Math. 38 (2024) 2001–2003.

[3] Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, Alexander Yu, Multitasking capacity: hardness results and improved constructions, SIAM J. Discrete Math. 34 (2020) 885–903.

[4] Noga Alon, Colin McDiarmid, Bruce A. Reed, Acyclic coloring of graphs, Random Struct. Algorithms 2 (1991) 277–288.

[5] Alon Noga, Ayal Zaks, Algorithmic aspects of acyclic edge colorings, Algorithmica 32 (2002) 611–614.

[6] Patrizio Angelini, Fabrizio Frati, Acyclically 3-colorable planar graphs, J. Comb. Optim. 24 (2012) 116–130.

[7] Aistis Atminas, Vadim V. Lozin, Igor Razgon, Linear time algorithm for computing a small biclique in graphs without long induced paths, in: Proceedings of SWAT 2012, in: LNCS, vol. 7357, 2012, pp. 142–152.
[8] Hans L. Bodlaender, A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput. 25 (1996) 1305-1317.

[9] Hans L. Bodlaender, Ton Kloks, Richard B. Tan, Jan van Leeuwen, Approximations for λ-colorings of graphs, Comput. J. 47 (2004) 193-204.

[10] Jan Bok, Nikola Jedličková, Barnaby Martin, Daniël Paulusma, Siani Smith, Acyclic colouring, star colouring and injective colouring for *H*-free graphs, in: Proc. ESA 2020, in: LIPLcs, vol. 173, 2020, pp. 22:1-22:22.

[11] Jan Bok, Nikola Jedličková, Barnaby Martin, Daniël Paulusma, Siani Smith, Injective colouring for *H*-free graphs, in: Proc. CSR 2021, in: LNCS, vol. 12730, 2021, pp. 18-30.

[12] Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma, Independent feedback vertex set for $P_5$-free graphs, Algorithmica 81 (2019) 1342-1369.

[13] Oleg V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211-236.

[14] Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma, Siani Smith, Acyclic, star and injective colouring: bounding the diameter, Electron. J. Comb. 2 (43) (2022).

[15] Hajo Broersma, Petr A. Golovach, Daniël Paulusma, Jian Song, Updating the complexity status of coloring graphs without a fixed induced linear forest, Theor. Comput. Sci. 414 (2012) 9-19.

[16] Tiziana Calamoneri, The *L*(h, k)-labelling problem: an updated survey and annotated bibliography, Comput. J. 54 (2011) 1344-1371.

[17] Christine T. Cheng, Eric McDermid, Ichiro Suzuki, Planarization and acyclic colorings of subcubic claw-free graphs, in: Proc. of WG 2011, in: LNCS, vol. 6986, 2011, pp. 107-118.

[18] Maria Chudnovsky, Sepehr Hajebi, Sophie Sprikl, *List*-k-coloring *H*-free graphs for all $k > 4$, Combinatorica 44 (2024) 1063-1068.

[19] Maria Chudnovsky, Shenwei Huang, Sophie Sprikl, Mingxian Zhong, *List*-three-coloring graphs with no induced $P_6 + rP_3$, Algorithmica 83 (2021) 216-251.

[20] Thomas F. Coleman, Jin-Yi Cai, The cyclic coloring problem and estimation of sparse Hessian matrices, SIAM J. Algebraic Discrete Methods 7 (1986) 221-235.

[21] Bruno Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inf. Comput. 85 (1990) 12-75.

[22] Zdeněk Dvořák, Bojan Mohar, Robert Šámal, Star chromatic index, J. Graph Theory 72 (2013) 313-326.

[23] Zdeněk Dvořák, Riste Šrekovski, Martin Tancer, *List*-coloring squares of sparse subcubic graphs, SIAM J. Discrete Math. 22 (2008) 139-159.

[24] Thomas Emden-Weinert, Stefan Hougardy, Bernd Kreuter, Uniquely colourable graphs and the hardness of colouring graphs of large girth, Comb. Probab. Comput. 7 (1998) 375-386.

[25] Paul Erdős, Graph theory and probability, Can. J. Math. 11 (1959) 34-38.

[26] Guillaume Fertin, Emmanuel Godard, André Raspaud, Minimum feedback vertex set and acyclic coloring, Inf. Process. Lett. 84 (2002) 131-139.

[27] Stephan Földes, Peter L. Hammer, Split graphs, Congr. Numer. 19 (1977) 311-315.

[28] Guillaume Fertin, André Raspaud, Acyclic coloring of graphs of maximum degree five: nine colors are enough, Inf. Process. Lett. 105 (2008) 65-72.

[29] Guillaume Fertin, André Raspaud, Bruce A. Reed, Star coloring of graphs, J. Graph Theory 47 (3) (2004) 163-182.

[30] Jiří Fiala, Petr A. Golovach, Jan Kratochvíl, Parameterized complexity of coloring problems: treewidth versus vertex cover, Theor. Comput. Sci. 412 (2011) 2513-2523.

[31] Jiří Fiala, Petr A. Golovach, Jan Kratochvíl, Bernard Lidický, Daniël Paulusma, Distance three labelings of trees, Discrete Appl. Math. 160 (2012) 764-779.

[32] Jiří Fiala, Ton Kloks, Jan Kratochvíl, Fixed-parameter complexity of lambda-labelings, Discrete Appl. Math. 113 (2001) 59-72.

[33] Esther Galby, Paloma T. Lima, Daniël Paulusma, Bernard Ries, Classifying k-edge colouring for H-free graphs, Inf. Process. Lett. 146 (2019) 39-43.

[34] Michael R. Garey, David S. Johnson, Larry J. Stockmeyer, Some simplified NP-complete graph problems, Theor. Comput. Sci. 1 (1976) 237-267.

[35] Petr A. Golovach, Matthew Johnson, Daniël Paulusma, Jian Song, A survey on the computational complexity of colouring graphs with forbidden subgraphs, J. Graph Theory 84 (2017) 331-363.

[36] Petr A. Golovach, Daniël Paulusma, Jian Song, Coloring graphs without short cycles and long induced paths, Discrete Appl. Math. 167 (2014) 107-120.

[37] Branko Grünbaum, Acyclic colorings of planar graphs, Isr. J. Math. 14 (1973) 390-408.

[38] Geňa Hahn, Jan Kratochvíl, Jozef Širán, Dominique Lotteau, On the injective chromatic number of graphs, Discrete Math. 256 (2002) 179-192.

[39] Pavol Hell, André Raspaud, Juraj Stacho, On injective colourings of chordal graphs, in: Proc. LATIN 2008, in: LNCS, vol. 4957, 2008, pp. 520-530.

[40] Ian Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 718-720.

[41] Shenwei Huang, Matthew Johnson, Daniël Paulusma, Narrowing the complexity gap for colouring ($C_s, P_t$)-free graphs, Comput. J. 58 (2015) 3074-3088.

[42] Robert Janczewski, Adrian Kosowski, Michal Malafiejski, The complexity of the *L*(p, q)-labeling problem for bipartite planar graphs of small degree, Discrete Math. 309 (2009) 3270-3279.

[43] Klaus Jansen, Complexity results for the optimum cost chromatic partition problem, Forschungsbericht 96-41, Mathematik/Informatik, Universität Trier, 1996.

[44] Jing Jin, Baogang Xu, Xiaoyan Zhang, On the complexity of injective colorings and its generalizations, Theor. Comput. Sci. 491 (2013) 119-126.

[45] Ross J. Kang, Tobias Müller, Frugal, acyclic and star colourings of graphs, Discrete Appl. Math. 159 (2011) 1806-1814.

[46] T. Karthick, Star coloring of certain graph classes, Graphs Comb. 34 (2018) 109-128.

[47] Tereza Klimošová, Josef Malik, Tomáš Masařík, Jana Novotná, Daniël Paulusma, Veronika Slívová, Colouring ($P_r + P_s$)-free graphs, in: Proc. ISAAC 2018, in: LIPLcs, 2018, pp. 123:5:1-5:13.

[48] Alexander V. Kostochka, Upper bounds of chromatic functions of graphs, PhD thesis, University of Novosibirsk, 1978.

[49] Daniel Král', Jan Kratochvíl, Zsolt Tuza, Gerhard J. Woeginger, Complexity of coloring graphs without forbidden induced subgraphs, in: Proc. WG 2001, in: LNCS, vol. 2204, 2001, pp. 254-262.

[50] Hoang La, Mickael Montassier, 2-distance 4-coloring of planar subcubic graphs with girth at least 21, Discrete Math. Theor. Comput. Sci. 26 (3) (2025), Article 19.

[51] Hui Lei, Yongtang Shi, Zi-Xia Song, Star chromatic index of subcubic multigraphs, J. Graph Theory 88 (2018) 566-576.

[52] Daniel Leven, Zvi Galil, NP-completeness of finding the chromatic index of regular graphs, J. Algorithms 4 (1983) 35-44.

[53] Cláudia Linhares-Sales, Ana Karolinna Maia, Nícolas A. Martins, Rudini Menezes Sampaio, Restricted coloring problems on graphs with few $P_4$'s, Ann. Oper. Res. 217 (2014) 385-397.

[54] Errol L. Lloyd, Subramanian Ramanathan, On the complexity of distance-2 coloring, in: Proc. ICCI 1992, 1992, pp. 71-74.

[55] Vadim V. Lozin, Marcin Kamiński, Coloring edges and vertices of graphs without short or long cycles, Contrib. Discrete Math. 2 (2007) 61-66.

[56] Andrew Lyons, Acyclic and star colorings of cographs, Discrete Appl. Math. 159 (2011) 1842-1850.

[57] Andrew Lyons, Restricted coloring problems and forbidden induced subgraphs, 2009, Manuscript.

[58] Mohammad Mahdian, On the computational complexity of strong edge coloring, Discrete Appl. Math. 118 (2002) 239-248.

[59] Debajyoti Mondal, Rahnuma Islam Nishat, Md. Saidur Rahman, Sue Whitesides, Acyclic coloring with few division vertices, J. Discret. Algorithms 23 (2013) 42-53.

[60] Pascal Ochem, Graph Coloring and Combinatorics on Words, PhD Thesis, Université de Bordeaux, 2005.

[61] Unabrahma Sen, Mark L. Huson, A new model for scheduling packet radio networks, Wirel. Netw. 3 (1997) 71-82.

[62] M.A. Shalu, Cyriac Antony, Complexity of restricted variant of star colouring, in: Proc. CALDAM 2020, in: LNCS, vol. 12016, 2020, pp. 3-14.

[63] David R. Wood, Acyclic, star and oriented colourings of graph subdivisions, Discret. Math. Theor. Comput. Sci. 7 (2005) 37-50.
[64] Xiao-Dong Zhang, Stanislaw Bylka, Disjoint triangles of a cubic line graph, Graphs Comb. 20 (2004) 275-280.

[65] Xiao Zhou, Yasuaki Kanari, Takao Nishizeki, Generalized vertex-coloring of partial k-trees, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 83-A (2000) 671-678.

[66] Enqiang Zhu, Zepeng Li, Zehui Shao, Jin Xu, Acyclically 4-colorable triangulations, Inf. Process. Lett. 116 (2016) 401-408.