Complexity of Injective Homomorphisms to Small Tournaments, and of Injective Oriented Colourings

Russell J. Campbell¹, Nancy E. Clarke², Gary MacGillivray³

¹University of the Fraser Valley, Abbotsford, British Columbia.
²Acadia University, Wolfville, Nova Scotia.
³University of Victoria, Victoria, British Columbia.

DOI: 10.4236/ojdm.2023.131001                

Abstract

Several possible definitions of local injectivity for a homomorphism of an oriented graph G to an oriented graph H are considered. In each case, we determine the complexity of deciding whether there exists such a homomorphism when G is given and H is a fixed tournament on three or fewer vertices. Each possible definition leads to a locally-injective oriented colouring problem. A dichotomy theorem is proved in each case.

Keywords

Injective Graph Homomorphism, Oriented Colouring, Complexity

1. Introduction

Three natural possible definitions of local injectivity of a homomorphism f from an input oriented graph G to a target oriented graph H are: for every vertex $x\in V\left(G\right)$, the function f is injective when restricted to:

1) The in-neighbourhood $N^{-}\left(x\right)$ ;

2) $N^{-}\left(x\right)$ and $N^{+}\left(x\right)$ separately;

3) The union $N^{-}\left(x\right)\cup N^{+}\left(x\right)$.

When H is reflexive, that is, has a loop at every vertex, the three definitions are different. When H is irreflexive, that is, has no loops, definitions 2 and 3 coincide. Each of these five situations leads naturally to a notion of locally- injective oriented k-colouring.

Locally-injective homomorphisms (as in possible definition 1) and colourings of oriented graphs were first introduced as an example in monadic second order logic [1]. Consequently, by Courcelle’s Theorem, these problems are all solvable in polynomial time when the input has bounded treewidth. The same holds for the other possible definitions above.

Possible definition 1 has been studied in previous papers for both irreflexive and reflexive targets [2] [3] [4] [5] [6]. A fairly complete theory has been developed. When the target, H, is reflexive there is a dichotomy theorem characterizing the oriented graphs H for which the problem of deciding the existence of a homomorphism to H is Polynomial, and those for which it is NP-complete. When H is irreflexive the complexity has been determined when H has maximum in-degree ${\Delta }^{-}\ge 3$ or ${\Delta }^{-}\le 1$ ; when ${\Delta }^{-}=2$ the situation is as rich as that for all digraph homomorphism problems, and hence all constraint satisfaction problems [5].

Possible definitions 2 and 3 have been studied in [7] [8]. Obstructions to (subgraphs that prevent the existence of) homomorphisms to small tournaments are the focus of [8]. Both definitions are considered. Possible definition 3 is the main focus of [7].

Locally-injective colourings of undirected graphs were first explicitly studied by Hahn, Kratochvil, Siřan and Sotteau [9]. Subsequent papers have considered chordal graphs [10], planar graphs (see [11]) and other graph classes, as well as list versions [12]. The complexity of locally-injective homomorphisms has been extensively studied by Fiala, Kratochvil, and others (e.g. see [13] [14]).

The purpose of this paper is to contribute to the theory of locally-injective homomorphisms and colourings under possible definitions 2 and 3 above. In each of the three cases that arise, the complexity of deciding the existence of a homomorphism to H is determined for the four tournaments on at most three vertices. These results appear in Sections 3, 4, and 5. Later, in Section 6, these results are then used to determine the complexity of the associated locally-injective oriented colouring problems.

We conclude this section by noting that the complexity of deciding whether a given directed graph G has a homomorphism to a tournament H has been studied [15]. There is a dichotomy theorem: the problem is Polynomial when H has at most one directed cycle, and NP-complete when H has at least two directed cycles. The results reported in this paper are first steps towards finding a similar theorem for locally-injective homomorphisms.

2. Notation and Terminology

An oriented graph is a directed graph G with the property that for any two different vertices x and y, at most one of the arcs $xy\mathrm{,}yx$ belongs to $E\left(G\right)$. An oriented graph G can be viewed as arising from a simple graph H by assigning a direction, or orientation, to each edge. The graph H is called the underlying graph of G, and G is referred to as an orientation of H. The converse of an oriented graph G is the oriented graph G^c with the same vertex set as G, and arc set $\left\{yx\mathrm{<mo>\; :\; </mo>}xy\in E\left(G\right)\right\}$.

An oriented graph is reflexive if it has a loop at each vertex, and irreflexive if it has no loops. The superscript “r”, as in $C_3^r$, indicates that the oriented graph under consideration is reflexive. Oriented graphs without this superscript, as in G, are irreflexive.

We use P_n, T_n, and T_n to denote the directed path on n vertices, the directed cycle on n vertices, and the transitive tournament on n vertices, respectively, $n\ge 1$. It will be assumed throughout that C₃ has vertex set $\left\{c_1\mathrm{,}{c}_2\mathrm{,}{c}_3\right\}$ and arc set $\left\{c_1{c}_2\mathrm{,}{c}_2{c}_3\mathrm{,}{c}_3{c}_1\right\}$, and that T_n has vertex set $\left\{t_0\mathrm{,}{t}_1\mathrm{,}\dots \mathrm{,}{t}_{n-1}\right\}$ and arc set $\left\{t_i{t}_j:i<j\right\}$.

A homomorphism of an oriented graph G to an oriented graph H is a function $f\mathrm{<mo>\; :\; </mo>}V\left(G\right)\to V\left(H\right)$ such that $f\left(x\right)f\left(y\right)\in E\left(H\right)$ whenever $xy\in E\left(G\right)$. When H has a loop, any directed graph has a homomorphism to H: map all vertices of G to a vertex of H with a loop. Thus, when loops are present, the existence of a homomorphism is a non-trivial question only in the presence of some side condition like selecting the image of each vertex from a list of possible images, or local injectivity. The book [16] contains a wealth of information about homomorphism of graphs and digraphs.

We call a homomorphism f of an oriented graph G to an oriented graph H:

• ios-injective if, for every vertex x of G, the restriction of f to $N^{-}\left(x\right)$ is injective, as is the restriction of f to $N^{+}\left(x\right)$ ; and

• iot-injective if, for every vertex x of G, the restriction of f to $N^{-}\left(x\right)\cup N^{+}\left(x\right)$ is injective.

These two concepts are the same when H is an irreflexive oriented graph, and different when H is a reflexive oriented graph.

The designations “ios” and “iot” arise from the local injectivity being on in- neighbourhoods and out-neighbourhoods separately, and on in-neighbourhoods and out-neighbourhoods together. In introducing the designations “ios” and “iot”, the qualifier “locally” has been dropped as it is part of the definition.

It is easy to see that the composition of two ios-injective homomorphisms is an ios-injective homomorphism, and similarly for iot-injective homomorphisms.

The following structure and its converse will be particularly useful. We define the hat H₃ to be the oriented graph with vertex set $V\left(H_3\right)=\left\{v_0\mathrm{,}{v}_1\mathrm{,}{v}_2\right\}$ and edge set $E\left(H_3\right)=\left\{v_0{v}_1\mathrm{,}{v}_2{v}_1\right\}$. See Figure 1. The vertices v₀ and v₂ will be referred to as the ends of H₃ or $H_3^c$. Whether or not H is reflexive, in an ios-injective or iot-injective homomorphism of H₃ or $H_3^c$ to H, the vertices v₀ and v₂ must have different images.

Figure 1. The hat and its converse.

3. Irreflexive Targets

In this section we show that, if T is an irreflexive tournament on at most 3 vertices, then the problem of deciding whether a given oriented graph has an ios-injective (and hence also iot-injective) homomorphism to T is Polynomial. A given oriented graph has an ios-injective homomorphism to T₁ if and only if it has no edges, and has an ios-injective homomorphism to T₂ if and only if it is a disjoint union of copies of T₁ and T₂. A given oriented graph, G, has an ios-injective homomorphism to C₃ if and only if it has maximum in-degree 1, maximum out-degree 1, and has a homomorphism to C₃. It follows that G has an ios-injective homomorphism to C₃ if and only if it is a disjoint union of directed paths, and directed cycles of length a multiple of 3. These conditions are easy to check in polynomial time. It remains to consider ios-injective homomorphisms to the transitive triple.

Proposition 3.1. The problem of deciding whether a given oriented graph has an ios-injective homomorphism to T₃ is Polynomial.

Proof. Let G be a given digraph. If the underlying graph of G has a vertex of degree 3 or more, then G has no ios-injective homomorphism to T₃. Hence assume that G is an orientation of a graph with maximum degree at most 2. Therefore the underlying graph of G is a disjoint union of paths and cycles, and hence has treewidth at most 2. Since ios-injective homomorphism is expressible in monadic second-order logic, the statement now follows from Courcelle’s Theorem.

4. Ios-Injective Homomorphisms to Small Reflexive Targets

In this section, we determine the complexity of deciding whether there exists an ios-injective homomorphism from a given oriented graph G to the fixed oriented graph H when H is one of the four reflexive tournaments on at most three vertices.

It is clear that an oriented graph G has an ios-injective homomorphism to $T_1^r$ if and only if it has maximum in-degree at most one and maximum out-degree at most one, that is, if and only if neither H₃ nor $H_3^c$ is a subgraph of G. Consequently, the only oriented graphs which have an ios-injective homomorphism to $T_1^r$ are disjoint unions of directed paths and directed cycles.

Proposition 4.1. The problem of deciding whether a given oriented graph has an ios-injective homomorphism to $T_2^r$ is Polynomial.

Proof. We describe a reduction to 2-SAT. Associate the vertices t₀ and t₁ of $T_2^r$ with false and true, respectively. Given an oriented graph G, the corresponding instance of 2-SAT has the set of variables $\left\{x_v\mathrm{<mo>\; :\; </mo>}v\in V\left(G\right)\right\}$. Since no oriented graph with a vertex of in-degree at least 3, or a vertex of out-degree at least 3, has an ios-injective homomorphism to $T_2^r$, we can assume that ${\Delta }^{+}\left(G\right)\le 2$ and ${\Delta }^{-}\left(G\right)\le 2$.

The set of clauses is constructed as follows.

1) If ${\text{deg}}^{+}\left(v\right)=2$, then $\neg x_v$ is a clause.

2) If ${\text{deg}}^{-}\left(v\right)=2$, then $x_v$ is a clause.

3) If $vw\in E$, then $\neg x_v\vee x_w$ is a clause.

4) If v and w are the ends of a copy of H₃ or $H_3^c$, then $x_v\vee x_w$ and $\neg x_v\vee \neg x_w$ are clauses.

All clauses in groups (1) and (2) are satisfied if and only if the image of any vertex of out-degree 2 is t₀ and the image of any vertex of in-degree 2 is t₁. All clauses in group (3) are satisfied if and only if the mapping corresponding to the truth assignment preserves arcs. And finally, all clauses in group (4) are satisfied if and only if the ends of a copy of H₃ or $H_3^c$ are assigned different images. It follows that there is an ios-injective homomorphism of G to $T_2^r$ if and only all clauses are satisfied.

We now show that the problem of deciding the existence of an ios-injective homomorphism to $C_3^r$ is NP-complete. Some “gadget” oriented graphs which map to $C_3^r$ only in special ways will be used in the NP-completeness proof. For an integer $d\ge 1$, the oriented graph D_d is constructed from a directed cycle $v_1\mathrm{,}{v}_2\mathrm{,}\dots \mathrm{,}{v}_{6d}\mathrm{,}{v}_1$ by adding the vertices $x_1\mathrm{,}{x}_2\mathrm{,}\dots \mathrm{,}{x}_{3d}$ and arcs $v_{2t}{x}_t\mathrm{,}{x}_t{v}_{2t-1}$, $t=1,2,\dots ,3d$.

Lemma 4.2. In an ios-injective homomorphism of D_d to $C_3^r$ the vertices $x_1\mathrm{,}{x}_4\mathrm{,}\dots \mathrm{,}{x}_{3d-2}$ all have the same image.

Proof. Let f be an ios-injective homomorphism of D_d to $C_3^r$. Without loss of generality, suppose $f\left(v_1\right)=c_1$. Then $f\left(v_2\right)$ is either c₁ or c₂.

Suppose first that $f\left(v_2\right)=c_1$. Then, observing that an ios-injective homomorphism of an irreflexive directed 3-cycle to $C_3^r$ either assigns every vertex the same image, or assigns no two vertices the same image, it must be that $f\left(x_1\right)=c_1$. By injectivity $f\left(v_3\right)\ne f\left(x_1\right)$, so $f\left(v_3\right)=c_2,$ the only other out-neighbour of c₁. It follows that $f\left(x_2\right)=c_2$. Similarly, $f\left(v_4\right)\ne c_3$, so that $f\left(v_4\right)=f\left(x_2\right)=c_2$. Continuing in this way, the vertices $v_1\mathrm{,}{v}_2\mathrm{,}\dots \mathrm{,}{v}_{6d}$ map to $c_1\mathrm{,}{c}_1\mathrm{,}{c}_2\mathrm{,}{c}_2\mathrm{,}{c}_3\mathrm{,}{c}_3\mathrm{,}{c}_1\mathrm{,}{c}_1\mathrm{,}\dots \mathrm{,}{c}_3\mathrm{,}{c}_3$, respectively, and the vertices $x_1\mathrm{,}{x}_2\mathrm{,}\dots \mathrm{,}{x}_{3d}$ map to $c_1\mathrm{,}{c}_2\mathrm{,}{c}_3\mathrm{,}{c}_1\mathrm{,}\dots \mathrm{,}{c}_3$, respectively.

Now suppose that $f\left(v_2\right)=c_2$. By our observation regarding homomorphisms of irreflexive directed 3-cycles, it must be that $f\left(x_1\right)=c_3$. Arguing as in the previous paragraph, ios-injectivity implies $f\left(v_3\right)=c_2,$ and $f\left(x_2\right)=c_1,$ which in turn implies $f\left(v_4\right)=c_3$. Continuing in this way, the vertices $v_1\mathrm{,}{v}_2\mathrm{,}\dots \mathrm{,}{v}_{6d}$ map to $c_1\mathrm{,}{c}_2\mathrm{,}{c}_2\mathrm{,}{c}_3\mathrm{,}{c}_3\mathrm{,}{c}_1\mathrm{,}{c}_1\mathrm{,}\dots \mathrm{,}{c}_3\mathrm{,}{c}_3\mathrm{,}{c}_1$, respectively, and the vertices $x_1\mathrm{,}{x}_2\mathrm{,}\dots \mathrm{,}{x}_{3d}$ map to $c_3\mathrm{,}{c}_1\mathrm{,}{c}_2\mathrm{,}{c}_3\mathrm{,}{c}_1\mathrm{,}\dots ,c_2$, respectively.

For $d\ge 2$, let X_d be the oriented graph constructed from D_d by adding d new vertices $n_1\mathrm{,}{n}_2\mathrm{,}\dots \mathrm{,}{n}_d$ and the arcs belonging to $\left\{x_{3i-2}{n}_i,n_i{x}_{3i+1}:i=1,2,\dots ,d\right\}$, where addition is modulo 3d. The following is a consequence of Lemma 4.2.

Corollary 4.3. In an ios-injective homomorphism of X_d to $C_3^r$, the vertices of the directed cycle $x_1\mathrm{,}{n}_1\mathrm{,}{x}_4\mathrm{,}{n}_2\mathrm{,}\dots \mathrm{,}{n}_d\mathrm{,}{x}_1$ must all be assigned the same image. Futher, any partial mapping in which these vertices are all assigned the same image can be extended to an ios-injective homomorphism of X_d to $C_3^r$ .

Theorem 4.4. The problem of deciding if a given oriented graph G has an ios-injective homomorphism to $C_3^r$ is NP-complete.

Proof. The transformation is from 3-colouring of graphs with minimum degree at least 3. Suppose a graph G is given. For each vertex $x\in V\left(G\right)$, regard the edges incident with x as being in 1-1 correspondence with the integers $\mathrm{1,2,}\dots \mathrm{,}{\text{deg}}_G\left(x\right)$ so that it is meaningful to talk about the i^th edge incident with x. Construct a digraph G' as follows. For each vertex $x\in V\left(G\right)$ there is a copy of $X_{{\text{deg}}_G\left(x\right)}$. (Note that ${\text{deg}}_G\left(x\right)\ge 3$.) Each edge of G is replaced by an oriented path on three vertices. Suppose $wz\in E\left(G\right)$ is the i^th edge incident with w and the j^th edge incident with z. Add a new vertex $u_{wz}$ and arcs from vertex $n_i$ of the copy of $X_{{\text{deg}}_G\left(w\right)}$ corresponding to w, and from vertex $n_j$ of the copy of $X_{{\text{deg}}_G\left(z\right)}$ corresponding to z, to $u_{wz}$. The transformation can be accomplished in polynomial time. We will show that G is 3-colourable if and only if there is an ios-injective homomorphism of G' to $C_3^r$.

Suppose that G is 3-colourable, and fix a 3-colouring using the colours $c_1\mathrm{,}{c}_2\mathrm{,}{c}_3$. If the colour of x is c_i, then map vertices $x_1\mathrm{,}{n}_1\mathrm{,}{x}_4\mathrm{,}{n}_2\mathrm{,}\dots \mathrm{,}{n}_d\mathrm{,}{x}_1$ of the copy of $X_{{\text{deg}}_G\left(x\right)}$ corresponding to x to c_i and extend this to an ios-injective homomorphism to $C_3^r$. The ends of each oriented path that replaced an edge of G are now assigned different images, and the mapping so far can be extended to the remaining vertex of each oriented path that replaced an edge of G.

Suppose G' has an ios-injective homomorphism to $C_3^r$. Then, in each copy of $X_{{\text{deg}}_G\left(x\right)}$, all vertices of the directed cycle $x_1\mathrm{,}{n}_1\mathrm{,}{x}_4\mathrm{,}{n}_2\mathrm{,}\dots \mathrm{,}{n}_{{\text{deg}}_G\left(w\right)}\mathrm{,}{x}_1$ are assigned the same image. Assign this colour to x. By the construction of G' and ios-injectivity, adjacent vertices of G are assigned different colours.

We conclude this section by showing that the problem of deciding whether a given oriented graph G has an ios-injective homomorphism to $T_3^r$ is NP-com- plete. A useful technical lemma is established first.

Lemma 4.5. Let F be the oriented graph in Figure 2. Then for $x\in \left\{t_0\mathrm{,}{t}_1\mathrm{,}{t}_2\right\}$, there exists an ios-injective homomorphism of F to $T_3^r$ that maps u to x, and any such homomorphism also maps v to x.

Proof. We sketch the proof that in an ios-injective homomorphism of F to $T_3^r$ that maps u to t₁, the vertex v also maps to t₁.

Referring to Figure 2, it is straightforward to check that in any ios-injective homomorphism of F to $T_3^r$, the vertices labelled $t_0\mathrm{,}{t}_2$ must map to $t_0\mathrm{,}{t}_2$, respectively. It is also easy to check that the vertices labelled a must have the same image, and similarly for the vertices labelled b, e and f. It will follow from the argument below that the vertices labelled c must have the same image, and similarly for the vertices labelled d.

We show that the vertices labelled t₁ must map to t₁. Suppose u maps to t₁. Then by injectivity its out-neighbour labelled c maps to t₀ or t₂. Since c has in-degree 2, it must map to t₂. Therefore d maps to t₀. The in-neighbour of c labelled t₁ must map to t₁ or t₂. But its in-neighbour labelled b has an out- neigh-bour labelled t₂, so the in-neighbour of c labelled t₁ must map to t₁. By

Figure 2. The oriented graph F in Lemma 4.5.

injectivity, the out-neighbour labelled a of this vertex must map to t₁, so the symmetrically located vertex labelled a must also map to t₁, and its in-neighbour labelled t₁ must map to t₁. A similar argument shows that the other vertices labelled t₁ must map to t₁.

We now show that v maps to t₁. By the above argument and injectivity, the vertex labelled c on the right of the figure maps to t₂. A symmetric argument shows that the vertex labelled d on the bottom of the figure must map to t₀. Now, by injectivity, v maps to t₁, as wanted.

Similar arguments show that if u maps to t₀ then so does v, and if u maps to t₂ then so does v.

Theorem 4.6. The problem of deciding if a given oriented graph has an ios-injective homomorphism to $T_3^r$ is NP-complete.

Proof. The transformation is from 3-edge colouring of cubic graphs [17]. Suppose such a graph G is given. Construct a graph G' as follows. For each $x\in V\left(G\right)$, regard the edges incident with x as being in 1-1 correspondence with the integers 1, 2, 3 so that it is meaningful to talk about the i^th edge incident with x.

Let H₄ denote the orientation of $K_{\mathrm{1,3}}$ in which there is a vertex of in-degree 3. In the sequel we refer to H₄ as an in-star. Start with a collection of $\left|V\left(G\right)\right|$ disjoint copies of H₄. Let S_x denote the copy of H₄ corresponding to vertex x. Regard the leaves of each oriented graph S_x to be in 1-1 correspondence with $\left\{\mathrm{1,2,3}\right\}$. Suppose $xy\in E\left(G\right)$ is the i^th edge incident with x and the j^th edge incident with y. Add a new copy of the oriented graph F shown in Figure 2 and identify the vertices labelled u and v having in-degree one with the i^th leaf of S_x and the j^th leaf of S_y. The transformation may be accomplished in polynomial time. We claim that G is 3-edge-colourable if and only if G' has an ios-injective homomorphism to $T_3^r$.

Suppose G has a 3-edge-colouring $f\mathrm{<mo>\; :\; </mo>}E\left(G\right)\to \left\{t_0\mathrm{,}{t}_1\mathrm{,}{t}_2\right\}$ (the colours are the vertices of $T_3^r$ ). For any edge xy of G, map the vertices labelled u and v in the corresponding copy of F to $f\left(xy\right)$. Finally, map the centre of each in-star of G' to its only possible image, t₂.

Conversely, suppose G' has an ios-injective homomorphism to T₃. For each edge xy of G, the vertices labelled u and v in the corresponding copy of F in G' must have the same image. Use this for the colour of xy. The resulting assignment is a 3-edge-colouring because the leaves of each in-star S_x in G' must have different images.

5. Iot-Injective Homomorphisms to Small Reflexive Targets

In this section we consider the complexity of deciding whether there exists an iot-injective homomorphism from a given oriented graph G to the fixed oriented graph H, when H is one of the four reflexive tournaments on at most three vertices.

It is clear that an oriented graph has an iot-injective homomorphism to $T_1^r$ if and only if it contains no oriented path on three vertices, that is, if and only if it is a disjoint union of copies of T₁ and T₂.

We now turn our attention to $T_2^r$. No orientation of a graph with a vertex of degree three has an iot-injective homomorphism to $T_2^r$. Thus, if G admits an iot-injective homomorphism to $T_2^r$, then the underlying graph of G is a disjoint union of paths and cycles. The following proposition can be proved using a reduction to 2-SAT, or by an appeal to Courcelle’s Theorem.

Proposition 5.1. The problem of deciding whether a given oriented graph has an iot-injective homomorphism to $T_2^r$ is Polynomial.

We next consider iot-injective homomorphism to $C_3^r$. Consider the family of oriented cycles $\mathcal{B}$ such that each $B\in \mathcal{B}$ is comprised of two disjoint perfect matchings oriented in opposite directions; that is, $V\left(B\right)=\left\{v_0\mathrm{,}{v}_1\mathrm{,}\dots \mathrm{,}{v}_{2k-1}\right\}$ and $E\left(B\right)\mathrm{<mo>\; =\; </mo>}\left\{v_0{v}_1\mathrm{,}{v}_2{v}_3\mathrm{,}\dots \mathrm{,}{v}_{2k-2}{v}_{2k-1}\right\}\cup \left\{v_0{v}_{2k-1}\mathrm{,}{v}_2{v}_1\mathrm{,}\dots \mathrm{,}{v}_{2k-2}{v}_{2k-3}\right\}$.

Lemma 5.2. Let $B\in \mathcal{B}$ have order n. Then (1) B has an iot-injective homomorphism to $C_3^r$ if and only if $n\equiv 0$ (mod 6), and (2) B has an iot- injective homomorphism to $T_3^r$ if and only if $n\equiv 0$ (mod 4).

Proof. Let $B\in \mathcal{B}$.

We first consider iot-injective homomorphism of B to $C_3^r$. Suppose B has n vertices. Let x be a vertex of out-degree two. Without loss of generality x maps to c₁. Then its out-neighbours map to c₁ and c₂. Let y be the out-neighbour that maps to c₁. Its out-neighbour must map to c₂. Continuing in this way, starting from x, the images of consecutive vertices are $c_1\mathrm{,}{c}_1\mathrm{,}{c}_2\mathrm{,}{c}_2\mathrm{,}{c}_3\mathrm{,}{c}_3\mathrm{,}{c}_1\mathrm{,}{c}_1\mathrm{,}\dots$. Therefore an iot-injective homomorphism exists if and only if $n\equiv 0$ (mod 6).

We now consider iot-injective homomorphism of B to $T_3^r$. Suppose B has n vertices. Let x be a vertex of out-degree two. Then x maps to t₀ or t₁.

Suppose first that x maps to t₀. Let v be an out-neighbour of x. If v were mapped to t₀, then its other in-neighbour must also map to t₀, in violation of injectivity. Therefore, the out-neighbours of x map to t₁ and t₂. Let y be the out-neighbour that maps to t₂. Then y’s other in-neighbour, z, must map to t₁ and z’s other out-neighbour, a, must also map to t₁. The vertex a has another in-neighbour, b. By injectivity, b maps to t₀. Continuing in this way, starting from x, the images of consecutive vertices are $t_0\mathrm{,}{t}_2\mathrm{,}{t}_1\mathrm{,}{t}_1\mathrm{,}{t}_0\mathrm{,}\dots ,t_0\mathrm{,}{t}_2\mathrm{,}{t}_1\mathrm{,}{t}_1\mathrm{,}{t}_0$. Therefore $n\equiv 0$ (mod 4).

Now suppose x maps to t₁. As above, the out-neighbours of x map to t₁ and t₂. Let y be the out-neighbour that maps to t₁. The vertex y has another in- neigh-bour, z, which by injectivity maps to t₀. Now, following the same argument as in the previous paragraph we have that, starting from x, the images of consecutive vertices are $t_1\mathrm{,}{t}_1\mathrm{,}{t}_0\mathrm{,}{t}_2\mathrm{,}{t}_1\mathrm{,}\dots ,t_1\mathrm{,}{t}_1\mathrm{,}{t}_0\mathrm{,}{t}_2\mathrm{,}{t}_1$. Again, $n\equiv 0$ (mod 4).

It now follows that an iot-injective homomorphism exists if and only if $n\equiv 0$ (mod 4).

Corollary 5.3. For $t\ge 1$, let $B_{6t}\in \mathcal{B}$ have 6t vertices. In any iot-injective homomorphism f of $B_{6t}$ to $C_3^r$ we have $f\left(v_i\right)=f\left(v_j\right)$, when $i\equiv j$ (mod 6).

Proof. This follows from the argument in Lemma 5.2.

Theorem 5.4. The problem of deciding whether an oriented graph has an iot-injective homomorphism to $C_3^r$ is NP-complete.

Proof. The transformation is from 3-colouring of connected graphs [18]. Suppose such a graph G is given. Construct a graph G' as follows. For each $x\in V\left(G\right)$, regard the edges incident with x as being in 1-1 correspondence with the integers $\mathrm{1,2,}\dots \mathrm{,}\text{deg}\left(x\right)$ so that it is meaningful to talk about the i^th edge incident with x. Replace every vertex $x\in V\left(G\right)$ with a copy R_x of $B_{6\cdot \text{deg}\left(x\right)}$ where, without loss of generality, the vertices $x_{6i}\in V\left(R_x\right)\mathrm{,}0\le i\le \text{deg}\left(x\right)-1$, have in-degree 2. Suppose xy is the i^th edge incident with x and the j^th edge incident with y. Construct an oriented path P_xy by adding a new vertex t_xy and joining each of $x_{6\left(i-1\right)}\in V\left(R_x\right)$ and $y_{6\left(j-1\right)}\in V\left(R_y\right)$ to it by adding a directed path of length two (the midpoint of each such directed path is a new vertex). The transformation can be carried out in polynomial time. We claim that G is 3-colourable if and only if G' has an iot-injective homomorphism to $C_3^r$.

Suppose G has a 3-colouring $f\mathrm{<mo>\; :\; </mo>}V\left(G\right)\to \left\{c_1\mathrm{,}{c}_2\mathrm{,}{c}_3\right\}$. For each vertex x, map the vertices $x_0\mathrm{,}{x}_6\mathrm{,}\dots ,x_{6\cdot \text{deg}\left(x\right)}$ of R_x to $f\left(x\right)$. By Corollary 5.3, this partial mapping extends to an iot-injective homomorphism of R_x to $C_3^r$. We claim that this mapping of the oriented cycles R_x extends to the oriented paths P_xy, where $xy\in E\left(G\right)$. Since adjacent vertices in G must receive different colours, this mapping of the copies of $B_{6\cdot \text{deg}\left(x\right)}$ assigns the vertices $v_0\mathrm{,}{v}_6\mathrm{,}\dots ,v_{6\cdot \text{deg}\left(x\right)}$ of R_x a different image than it assigns the corresponding vertices of R_y. Suppose, without loss of generality, that the vertices $v_0\mathrm{,}{v}_6\mathrm{,}\dots ,v_{6\cdot \text{deg}\left(x\right)}$ of R_x are mapped to c₁ and the corresponding vertices of R_y are mapped to c₂. The in-neighbours of the vertices in R_x are mapped to c₁ and c₃, while the neighbours of the corresponding vertices in R_y are mapped to c₂ and c₁. The vertex t_xy can be mapped to c₃ and the assignment extended to an iot-injective homomorphism of P_xy to $C_3^r$. This proves the claim, and completes the proof of the implication.

On the other hand, suppose G' has an iot-injective homomorphism to $C_3^r$. Fix such a mapping. Then, for each $v\in V\left(G\right)$, the vertices $v_0\mathrm{,}{v}_6\mathrm{,}\dots ,v_{6\cdot \text{deg}\left(v\right)}\in V\left(R_v\right)$ all have the same image; assign this to be the colour of vertex v of G.

We claim that vertices x and y that are adjacent in G are assigned different colours. Suppose not. By symmetry of $C_3^r$, assume both are assigned c₁. Suppose also that xy is the i-th edge incident with x and the j-th edge incident with y. Then, the vertices $x_{6\left(i-1\right)}\in V\left(R_x\right)$ and $y_{6\left(j-1\right)}\in V\left(R_y\right)$ both map to c₁. By construction, $x_{6\left(i-1\right)}$ has two in-neighbours in R_x and one out-neighbour on the directed path to t_xy, and similarly for $y_{6\left(j-1\right)}$. Since both $x_{6\left(i-1\right)}$ and $y_{6\left(j-1\right)}$ map to c₁, in each case their in-neighbours must map to c₁ and c₃. By injectivity, in each case their out-neighbour on the directed path to t_xy must map to c₂. Therefore t_xy has 2 in-neighbours that map to c₂, which violates injectivity. This proves the claim, and completes the proof.

Finally, we consider iot-injective homomorphism to $T_3^r$. The following lemma can be proved similarly to Lemma 4.5. The proof of Lemma 4.5 relies only on injectivity on in-neighbourhoods or out-neighbourhoods, and never both at the same vertex.

Lemma 5.5. Let F be the oriented graph in Figure 2. Then For $x\in \left\{t_0\mathrm{,}{t}_1\mathrm{,}{t}_2\right\}$, there exists an iot-injective homomorphism of F to $T_3^r$ that maps u to x, and any such homomorphism also maps v to x.

The proof of the following theorem is similar to that of Theorem 4.6 and is omitted. For details, see [7].

Theorem 5.6. The problem of deciding whether an oriented graph has an iot-injective homomorphism to $T_3^r$ is NP-complete.

6. Colourings

Recall that a (proper) oriented k-colouring of an oriented graph G is a homomorphism to a tournament on k vertices. We therefore make the following definitions:

1) A proper ios-injective oriented k-colouring of an oriented graph G is an ios-injective homomorphism to an irreflexive tournament on k vertices.

2) An improper ios-injective oriented k-colouring of an oriented graph G is an ios-injective homomorphism to a reflexive tournament on k vertices.

3) An improper iot-injective oriented k-colouring of an oriented graph G is an iot-injective homomorphism to a reflexive tournament on k vertices.

A proper iot-injective oriented k-colouring of a graph G would be an iot- injective homomorphism to an irreflexive tournament on k vertices. Since tournaments have no directed 2-cycles, these are the same as proper ios-injective oriented k-colourings.

For each fixed integer k and each injective colouring problem defined above, we will determine the complexity of deciding whether a given oriented graph G has an injective colouring with k colours. The approach to proving NP- completeness is similar to that for oriented colourings that are injective on in- neighbourhoods [2] [6]: prove that it is NP-complete to decide the existence of an injective homomorphism of the given type to the tournament $U_m\mathrm{,}m\ge 4$, that consists of a directed three cycle dominated by every vertex of a transitive tournament of size $m-3$, and then obtain the desired result as a corollary. We consider the three situations in turn after establishing a useful lemma.

Lemma 6.1. Let G be an oriented graph such that U_m is a subgraph of G. For $\mathcal{P}\in \left\{\text{ios},\text{iot}\right\}$, if G has a $\mathcal{P}$ -injective homomorphism to a tournament T (respectively, reflexive tournament $T^r$ ), then U_m (respectively, $U_m^r$ ) is a subgraph of T.

Proof. The tournament U_m has the property that every two different vertices have a common in-neighbour or a common out-neighbour. Hence no two of its vertices can be assigned the same image by a $\mathcal{P}$ -injective homomorphism. Consequently, the image of G must contain U_m.

6.1. Proper Ios-Injective Colourings

Theorem 6.2. For each fixed $m\ge 4$, the problem of deciding if a given oriented graph has an ios-injective homomorphism to U_m is NP-complete.

Proof. We first show that the problem of deciding whether a given oriented graph G has an ios-injective homomorphism to U₄ is NP-complete. The transformation is from the problem of deciding if a given cubic graph is 3-edge- colourable [17]. Let G be a given cubic graph. Construct an oriented graph G' by replacing each edge xy of G by an oriented path P_xy with vertices $x\mathrm{,}{v}_1\mathrm{,}{v}_2\mathrm{,}{v}_3\mathrm{,}{v}_4\mathrm{,}y$ and arcs $x{v}_1\mathrm{,}{v}_1{v}_2\mathrm{,}{v}_2{v}_3\mathrm{,}{v}_3{v}_4\mathrm{,}y{v}_4$. The transformation can be accomplished in polynomial time. We claim that G is 3-edge-colourable if and only if there is an ios-injective homomorphism of G' to U₄.

Suppose that G is 3-edge colourable. Then, for each vertex x of G, each of the colours 1, 2 and 3 appears on an edge incident with x. An ios-injective homomorphism of G' to U₄ is obtained by mapping all vertices of G to the vertex of out-degree 3 in U₄, assigning the colour of the edge xy to the vertices v₁ and v₄ of P_xy, and extending this pre-colouring to the vertices v₂ and v₃ of P_xy.

Suppose that there is an ios-injective homomorphism of G' to U₄. Every vertex of G has out-degree 3 in G', so an ios-injective homomorphism of G' to U₄ must map it to the unique vertex of out-degree 3 in U₄. Similarly, the vertices v₁, v₂, v₃, and v₄ in each oriented path P_xy have positive in-degree in G', so an ios-injective homomorphism of G' to U₄ must map each of them to a vertex of the directed 3-cycle. In any such mapping, v₁ and v₄ map to the same vertex, and the three out-neighbours of each vertex of G (in G') map to different vertices of the 3-cycle. Assigning each edge xy of G the image of the vertex v₁ (and v₄) in P_xy gives a 3-edge-colouring of G.

NP-completeness of ios-injective homomorphism to U_m follows from NP- completeness of ios-injective homomorphism to U₄. Given an instance G of ios-injective homomorphism to U₄, construct G' by adding the new vertices belonging to $V^{\prime }=\left\{x_i:x\in V\left(G\right),i=1,2,\dots ,\left(m-4\right)-d^{-}\left(x\right)\right\}$ and the arcs $\left\{x_{i}x:x\in V\left(G\right),i=1,2,\dots ,\left(m-4\right)-d^{-}\left(x\right)\right\}$. Since m is a constant, the transformation can be accomplished in polynomial time. Each vertex of G in G' has in-degree $m-4$ and therefore cannot map to the $m-4$ vertices of U_m with in-degree less than $m-4$. An ios-injective homomorphism of G to U₄ can be extended to an ios-injective homomorphism of G' to U_m.

Corollary 6.3. Let k be a fixed positive integer. If $k\le 3$, the problem of deciding if a given oriented graph G has a proper ios-injective oriented k- colouring is Polynomial. If $k\ge 4$, the problem of deciding if a given oriented graph G has a proper ios-injective oriented k-colouring is NP-complete.

Proof. An oriented graph G has a proper ios-injective oriented k-colouring if and only if $G\cup U_k$ has an ios-injective homomorphism to U_k.

6.2. Improper Ios-Injective Colourings

Theorem 6.4. For each fixed $m\ge 4$, the problem of deciding if a given oriented graph has an ios-injective homomorphism to $U_m^r$ is NP-complete.

Proof. The transformation is from the problem of deciding whether there exists an ios-injective homomorphism of a given oriented graph G to $C_3^r$, which is NP-complete by Theorem 4.4. Suppose the oriented graph G is given. We may assume that ${\Delta }^{+}\left(G\right)\le 2$ and ${\Delta }^{-}\left(G\right)\le 2$, otherwise G cannot have an ios-in-jective homomorphism to $C_3^r$.

Construct G' from G as follows. For each $x\in V\left(G\right)$, if x has in-degree at most one in G, add a set of $m-2$ new vertices and arcs joining each of them to x. If x has in-degree two in G, do the same using a set of $m-3$ new vertices. The transformation can be accomplished in polynomial time. We claim that G has an ios-injective homomorphism to $C_3^r$ if and only if G' has an ios-injective homomorphism to $U_m^r$.

An ios-injective homomorphism of G to $C_3^r$ can clearly be extended to an ios-injective homomorphism of G' to $U_m^r$.

Suppose f is an ios-injective homomorphism of G' to $U_m^r$. Since each vertex $x\in V\left(G\right)$ has in-degree at least $m-1$ in G' and every vertex of $U_m^r$ not belonging to the copy of $C_3^r$ has in-degree at most $m-3$, the vertex x must map to a vertex of the directed 3-cycle in $U_m^r$. The restriction of f to $V\left(G\right)$ is the desired mapping.

Corollary 6.5. Let k be a fixed integer. If $k\le 2$, the problem of deciding if a given oriented graph G has an improper ios-injective oriented k-colouring is Polynomial. If $k\ge 3$, the problem of deciding if a given oriented graph G has an improper ios-injective oriented k-colouring is NP-complete.

Proof. When $k=3$ the transformation is from the problem of deciding whether there exists an ios-injective homomorphism of a given oriented graph G to $C_3^r$, which is NP-complete by Theorem 4.4. Since there is no ios-injective homomorphism of D_d (from Lemma 4.2) to $T_3^r$, an oriented graph G has an improper ios-injective oriented 3-colouring if and only if $G\cup D_6$ has an ios-injective homomorphism to $C_3^r$.

When $k\ge 4$, the transformation is from the problem of deciding whether there exists an ios-injective homomorphism of a given oriented graph G to $U_k^r$. Given an oriented graph G, the transformed instance of improper ios-injective oriented k-colouring is the oriented graph $G\cup U_k$. The claim that this graph has an improper ios-injective oriented k-colouring if and only if G has an ios-injective homomorphism to $U_k^r$ follows from Lemma 6.1. $\square$

6.3. Improper Iot-Injective Colourings

Theorem 6.6. For each fixed $m\ge 4$, the problem of deciding if a given oriented graph has an improper iot-injective homomorphism to $U_m^r$ is NP-complete.

Proof. The transformation is from the problem of deciding whether there exists an iot-injective homomorphism of a given oriented graph G to $C_3^r$, which is NP-complete by Theorem 4.4. Given an oriented graph G, the transformed instance G' is constructed by starting with G and proceeding as follows. For each vertex $x\in V\left(G\right)$, add a copy of $T_{m-3}$ and arcs from each of its vertices to x. Then for every vertex t of each copy of $T_{m-3}$ that was added, add three vertices, $t_a\mathrm{,}{t}_b\mathrm{,}{t}_c$, and arcs from t to each of them. The oriented graph G has an iot-injective $C_3^r$ -colouring if and only if G' has an iot-injective $U_m^r$ -colouring.

The proof of the following is identical to that of Corollary 6.5, except for replacing “ios” by “iot”.

Corollary 6.7. Let k be a fixed integer. If $k\le 2$, the problem of deciding whether an oriented graph has an improper iot-injective k-colouring is Polynomial. If $k\ge 3$, the problem of deciding whether an oriented graph has an improper iot-injective k-colouring is NP-complete.

For a given oriented graph G, we denote by ${\chi }_{ios}\left(G\right)\mathrm{,}{\chi }_{ios}^r\left(G\right)$ and ${\chi }_{iot}^r\left(G\right)$, the smallest number of colours in a proper ios-injective oriented colouring, an improper ios-injective oriented colouring, and an improper iot-injective oriented colouring of G, respectively. The superscript “r” is used to designate the improper colourings because the target graph being reflexive is what allows adjacent vertices to be assigned the same colour. A project for future research is to find tight bounds for these parameters. The upper bounds should be exponential in the in-degree and out-degree consider the disjoint union of all tournaments on a fixed number of vertices. Weak upper bounds can be obtained using the methods in [2] [4] [6] [7]. Tight bounds and efficient algorithms for trees can be obtained as in [2] [4] [7].

Supported

Research of the 2^nd and 3^rd authors supported by NSERC.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Courcelle, B. (1994) The Monadic Second Order Logic of Graphs VI: On Several Representations of Graphs by Relational Structures. Discrete Applied Mathematics, 54, 117-149. https://doi.org/10.1016/0166-218X(94)90019-1
[2]	MacGillivray, G., Raspaud, A. and Swarts, J. (2009) Injective Oriented Colourings. Graph Theoretic Concepts in Computer Science, 35th International Workshop WG, Lecture Notes in Computer Science, Vol. 5911, Montpellier, 24-26 June 2009, 262-272. https://doi.org/10.1007/978-3-642-11409-0_23
[3]	MacGillivray, G., Raspaud, A. and Swarts, J. (2011) Obstructions to Injective Oriented Colourings. Proceedings of EuroComb 2011, Electronic Notes in Discrete Mathematics, Vol. 38, Budapest, 29 August-2 September 2011, 597-605. https://doi.org/10.1016/j.endm.2011.10.001
[4]	MacGillivray, G., Raspaud, A. and Swarts, J. (2014) Obstructions to Locally Injective Oriented Improper Colourings. European Journal of Combinatorics, 35, 402-412. https://doi.org/10.1016/j.ejc.2013.06.023
[5]	MacGillivray, G. and Swarts, J. (2010) The Complexity of Locally Injective Homomorphisms. Discrete Mathematics, 310, 2685-2696. https://doi.org/10.1016/j.disc.2010.03.034
[6]	Swarts, J. (2008) The Complexity of Digraph Homomorphisms: Local Tournaments, Injective Homomorphisms and Polymorphisms. Ph.D. Thesis, University of Victoria, Victoria.
[7]	Campbell, R.J. (2009) Reflexive Injective Oriented Colourings. M.Sc. Thesis, University of Victoria, Victoria, BC, Canada.
[8]	Campbell, R.J., Clarke, N. and MacGillivray, G. (2022) Obstructions to Some Injective Oriented Colourings. https://arxiv.org/abs/2207.12523v1
[9]	Hahn, G., Kratochvil, J., Širáň, J. and Sotteau, D. (2002) On the Injective Chromatic Number of Graphs. Discrete Mathematics, 256, 179-192. https://doi.org/10.1016/S0012-365X(01)00466-6
[10]	Hell, P., Raspaud, A. and Stacho, J. (2008) On Injective Colourings of Chordal Graphs. In: Laber, E.S., et al., Eds., LATIN 2008: Theoretical Informatics, Lecture Notes in Computer Science Vol. 4957, Springer, Berlin, 520-530. https://doi.org/10.1007/978-3-540-78773-0_45
[11]	Kratochvíl, J. and Siggers, M. (2014) Locally Injective k-Colourings of Planar Graphs. Discrete Applied Mathematics, 173, 53-61. https://doi.org/10.1016/j.dam.2014.03.020
[12]	Fiala, J. and Kratochvíl, J. (2006) Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy. In: Fomin, F.V., Ed., Graph Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 4271, Springer, Berlin, 15-26. https://doi.org/10.1007/11917496_2
[13]	Fiala, J., Kratochvíl, J. and Pór, A. (2008) On the Computational Complexity of Partial Covers of Theta Graphs. Discrete Applied Mathematics, 156, 1143-1149. https://doi.org/10.1016/j.dam.2007.05.051
[14]	Fiala, J., Paulusma, D. and Telle, J.A. (2008) Locally Constrained Graph Homomorphisms and Equitable Partitions. European Journal of Combinatorics, 29, 850-880. https://doi.org/10.1016/j.ejc.2007.11.006
[15]	Bang-Jensen, J., Hell, P. and MacGillivray, G. (1988) The Complexity of Colourings by Semicomplete Digraphs. SIAM Journal on Discrete Mathematics, 1, 291-298. https://doi.org/10.1137/0401029
[16]	Hell, P. and Nešetřil, J. (2004) Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and Its Applications, Vol. 28, Oxford University Press, Oxford.
[17]	Holyer, I. (1981) The NP-Completeness of Edge-Coloring. SIAM Journal on Computting, 10, 718-720. https://doi.org/10.1137/0210055
[18]	Garey, M.R., Johnson, D.S. and Stockmeyer, L. (1976) Some Simplified NP-Complete Graph Problems. Theoretical Computer Science, 1, 237-267. https://doi.org/10.1016/0304-3975(76)90059-1