# On the Oriented Chromatic Index of Oriented Graphs

Pascal Ochem, Alexandre Pinlou, Eric Sopena

► To cite this version:

Pascal Ochem, Alexandre Pinlou, Eric Sopena. On the Oriented Chromatic Index of Oriented Graphs. Journal of Graph Theory, 2008, 57 (4), pp.313-332. 10.1002/jgt.20286. lirmm-00195956

HAL Id: lirmm-00195956

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00195956

Submitted on 18 Sep 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished 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
# On the Oriented Chromatic Index of Oriented Graphs

Pascal Ochem,¹ Alexandre Pinlou,²* and Éric Sopena³

¹UNIVERSITÉ PARIS-SUD
LRI, 91405 ORSAY CEDEX, FRANCE

E-mail: pascal.ochem@lri.fr

²UNIVERSITÉ MONTPELLIER 3
LIRMM, 161 RUE ADA, 34392 MONTPELLIER CEDEX 5, FRANCE

E-mail: alexandre.pinlou@lirmm.fr

³UNIVERSITÉ BORDEAUX 1
LABRI, 351 COURS DE LA LIBÉRATION, 33405 TALENCE CEDEX, FRANCE

E-mail: eric.sopena@labri.fr

Received July 5, 2006; Revised October 8, 2007

Published online 26 December 2007 in Wiley InterScience(www.interscience.wiley.com).

DOI 10.1002/jgt.20286

**Abstract:** A homomorphism from an oriented graph $G$ to an oriented graph $H$ is a mapping $\varphi$ from the set of vertices of $G$ to the set of vertices of $H$ such that $\varphi(u)\varphi(\overrightarrow{v})$ is an arc in $H$ whenever $\overrightarrow{uv}$ is an arc in $G$. The oriented chromatic index of an oriented graph $G$ is the minimum number of vertices in an oriented graph $H$ such that there exists a homomorphism from the line digraph $LD(G)$ of $G$ to $H$ (the line digraph $LD(G)$ of $G$ is given by $V(LD(G)) = A(G)$ and $ab \in A(LD(G))$ whenever $a = \overrightarrow{uv}$ and $b = \overrightarrow{vw}$).

We give upper bounds for the oriented chromatic index of graphs with bounded acyclic chromatic number, of planar graphs and of graphs with bounded degree. We also consider lower and upper bounds of oriented chromatic number in terms of oriented chromatic index. We finally prove that the problem of deciding whether an oriented graph has oriented chromatic index at most $k$ is polynomial time solvable if $k \le 3$ and is NP-complete if $k \ge 4$. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 313–332, 2008

Keywords: oriented graph; oriented coloring; arc coloring

<footnote>*Département Mathématiques et Informatique Appliqués, Université Paul-Valéry, Montpellier 3, Route de Mende, 34199 Montpellier, France.</footnote>
# 1. INTRODUCTION

We consider finite simple *oriented graphs*, that are digraphs with no opposite arcs. For an oriented graph $G$, we denote by $V(G)$ its set of vertices and by $A(G)$ its set of arcs. For two adjacent vertices $u$ and $v$, we denote by $\vec{uv}$ the arc from $u$ to $v$ or simply $uv$ whenever its orientation is not relevant (therefore, $uv = \vec{uv}$ or $uv = \overrightarrow{uv}$).

The notion of oriented vertex-coloring was introduced by Courcelle [7] as follows: an *oriented $k$-vertex-coloring* of an oriented graph $G$ is a mapping $\varphi$ from $V(G)$ to a set of $k$ colors such that (i) $\varphi(u) \neq \varphi(v)$ whenever $\vec{uv} \in A(G)$ and (ii) $\varphi(v) \neq \varphi(x)$ whenever $\vec{uv}, \overline{xy} \in A(G)$ and $\varphi(u) = \varphi(y)$. The *oriented chromatic number* of $G$, denoted by $\chi_o(G)$, is defined as the smallest $k$ such that $G$ admits an oriented $k$-vertex-coloring. The notion of oriented chromatic number can be extended to graph classes: the oriented chromatic number $\chi_o(F)$ of a class of oriented graphs $F$ is defined as the maximum of $\chi_o(G)$ taken over all graphs $G$ in $F$. Observe that conditions (i) and (ii) above ensure that two vertices linked by a directed path of length one or two must get distinct colors in any oriented vertex-coloring.

Let $G$ and $H$ be two oriented graphs. A *homomorphism* from $G$ to $H$ is a mapping $\varphi$ from $V(G)$ to $V(H)$ that preserves the arcs: $\varphi(\overrightarrow{uv})\varphi(\overrightarrow{vw}) \in A(H)$ whenever $\vec{uv} \in A(G)$. An oriented $k$-vertex-coloring of an oriented graph $G$ can be equivalently defined as a homomorphism $\varphi$ from $G$ to $H$, where $H$ is an oriented graph of order $k$. The existence of such a homomorphism from $G$ to $H$ is denoted by $G \to H$. The vertices of $H$ are called *colors*, and we say that $G$ is $H$-colorable. The oriented chromatic number of $G$ can then be equivalently defined as the smallest order of an oriented graph $H$ such that $G \to H$. Links between colorings and homomorphisms are presented in more details in the recent monograph [12] by Hell and Nešetřil.

Oriented vertex-colorings have been studied by several authors in the last decade and the problem of bounding the oriented chromatic number has been investigated for graphs with bounded acyclic chromatic number [21], graphs with bounded maximum average degree [6], graphs with bounded degree [15], graphs with bounded treewidth [22,23], and graph subdivisions [24].

One can define *oriented arc-colorings* of oriented graphs in a natural way by saying that, as in the undirected case, an oriented arc-coloring of an oriented graph $G$ is an oriented vertex-coloring of its line digraph $LD(G)$ (recall that $LD(G)$ is given by $V(LD(G)) = A(G)$ and $\overrightarrow{ab} \in A(LD(G))$ whenever $a = \vec{uv}$ and $b = \overrightarrow{vw}$). We say that an oriented graph $G$ is *$H$-arc-colorable* if there exists a homomorphism $\varphi$ from $LD(G)$ to $H$ and $\varphi$ is then an *$H$-arc-coloring* or simply an *arc-coloring* of $G$. Therefore, an oriented arc-coloring $\varphi$ of $G$ must satisfy (i) $\varphi(\vec{uv}) \neq \varphi(\overrightarrow{vw})$ whenever $\vec{uv}$ and $\overrightarrow{vw}$ are two consecutive arcs in $G$, and (ii) $\varphi(\overrightarrow{vw}) \neq \varphi(\overline{xy})$ whenever $\vec{uv}, \overrightarrow{vw}, \overline{xy}, \overrightarrow{yz} \in A(G)$ with $\varphi(\vec{uv}) = \varphi(\overrightarrow{yz})$. Note that these two conditions ensure that two arcs belonging to a directed path of length two or three must get distinct colors in any oriented arc-coloring. Also note that two incident but non-consecutive arcs (i.e., two arcs incoming into a same vertex or two arcs outgoing from a same vertex) can get the same color since the two corresponding vertices in $LD(G)$ are
not adjacent and does not belong to a directed 2-path. The *oriented chromatic index* of *G*, denoted by $\chi_o'(G)$, is defined as the smallest order of an oriented graph *H* such that $\text{LD}(G) \to H$. Therefore, $\chi_o'(G) = \chi_o(\text{LD}(G))$. The oriented chromatic index $\chi_o'(\mathcal{F})$ of a class of oriented graphs $\mathcal{F}$ is defined as the maximum of $\chi_o'(G)$ taken over all graphs *G* in $\mathcal{F}$.

The first easy result concerning oriented arc-coloring relates the oriented chromatic index to the oriented chromatic number:

**Observation 1.** Let *G* be an oriented graph. Then $\chi'_{o}(G) \le \chi_{o}(G)$.

To see that, consider an oriented graph *G* with $\chi_o(G) = k$ and an oriented $k$-vertex-coloring *f* of *G*. The mapping *g* defined by $g(\vec{uv}) = f(u)$ for every arc $\vec{uv} \in A(G)$ is clearly an oriented arc-coloring of *G*.

Therefore, all upper bounds for the oriented chromatic number are also valid for the oriented chromatic index. In this article, we provide better upper bounds for the oriented chromatic index of several classes of graphs and consider the complexity of the oriented arc-coloring problem.

A weaker version of arc-coloring of oriented graphs where condition (ii) is dropped has been considered [2,11]. The corresponding chromatic number is thus $\chi(\text{LD}(G))$. Various other types of arc-colorings were considered in the literature (see e.g., [10,13]).

This article is organized as follows. The link between oriented chromatic index and acyclic chromatic number is discussed in Section 2. The oriented chromatic index of planar graphs and of graphs with bounded degree are respectively considered in Sections 3 and 4. In Section 5, we investigate lower and upper bounds of the oriented chromatic number in terms of the oriented chromatic index. Finally, the complexity of determining the oriented chromatic index of a graph is studied in Section 6.

In the rest of the article, we will use the following notions. A vertex of degree *k* will be called a *k*-vertex. If $\vec{uv}$ is an arc, *u* is a *predecessor* of *v* and *v* is a *successor* of *u*. A vertex will be called a *source* if it has no predecessors and a *sink* if it has no successors.

For a graph *G* and a vertex *v* of *V*(*G*), we denote by *G* \ *v* the graph obtained from *G* by removing *v* together with the set of its incident arcs. This notion is extended to sets of vertices in a standard way.

Let *G* be an oriented graph and *f* be an oriented arc-coloring of *G*. For a given vertex *v* of *G*, we denote by $C_f^+(v)$ and $C_f^-(v)$ the *outgoing color set* of *v* (i.e., the set of colors of the arcs outgoing from *v*) and the *incoming color set* of *v* (i.e., the set of colors of the arcs incoming to *v*), respectively.

## 2. ORIENTED CHROMATIC INDEX AND ACYCLIC CHROMATIC NUMBER

A proper vertex-coloring of an undirected graph *G* is *acyclic* if every subgraph induced by any two color classes is a forest (in other words, the graph has no
bichromatic cycle). The *acyclic chromatic number* of G, denoted by $\chi_a(G)$, is the smallest $k$ such that G admits an acyclic $k$-vertex-coloring.

One of the first problems considered for oriented vertex-colorings was to characterize the families of graphs having bounded-oriented chromatic number. It was shown that these families are exactly the ones having bounded acyclic chromatic number [15,21].

In particular, Raspaud and Sopena [21] proved that every oriented graph whose underlying undirected graph has acyclic chromatic number at most $k$ has oriented chromatic number at most $k \cdot 2^{k-1}$. Recently, Ochem [18] proved that this bound is tight by constructing, for every $k \ge 3$, an oriented graph $G$ such that $\chi_a(G) = k$ and $\chi_o(G) = k \cdot 2^{k-1}$.

By Observation 1, every oriented graph with acyclic chromatic number $k$ has oriented chromatic index at most $k \cdot 2^{k-1}$. By adapting the proof of the above-mentioned result of Raspaud and Sopena, we get a new upper bound which is quadratic in terms of the acyclic chromatic number:

**Theorem 2.** Every oriented graph whose underlying undirected graph has acyclic chromatic number at most $k$ has oriented chromatic index at most $2k(k-1) - \lfloor \frac{k}{2} \rfloor$.

To show that, we need the two following lemmas:

**Lemma 3.** Let $F$ be an oriented forest. Then $F$ admits a $C_3$-arc-coloring where $C_3$ is the directed cycle on three vertices.

*Proof.* For each connected component $G$, choose one arc and color it with the color 0. Then, as long as it remains uncolored, choose a vertex $u$ with at least one incident arc $uv$ colored with color $c$. If $\overrightarrow{uv} \in G$ (resp. $\overrightarrow{uv} \in G$), then color all outgoing (resp. incoming) arcs from $u$ with the color $c$ and all incoming (resp. outgoing) arcs from $u$ with the color $c-1 \pmod 3$ (resp. $c+1 \pmod 3$). This arc-coloring is clearly a $C_3$-arc-coloring.

**Lemma 4.** Let $F$ be a forest, $c$ be a 2-vertex-coloring of $F$ using $i$ and $j$ ($i < j$), and $\overrightarrow{F}$ be any orientation of $F$. There exists an oriented 4-arc-coloring $f$ of $\overrightarrow{F}$ using $\{i, j\} \times \{0, 1\}$ such that for every vertex $u$, $c(u)$ and the first component of $f(\overrightarrow{u\upsilon})$ coincide, for each $\overrightarrow{u\upsilon} \in A(F)$.

*Proof.* The coloring $f$ can easily be obtained from $c$ by using the following rule: if $\overrightarrow{u\upsilon}$ and $\overrightarrow{v\upsilon}$ are two consecutive arcs in $\overrightarrow{F}$, then let $f(\overrightarrow{u\upsilon}) = (c(u), \alpha)$ and $f(\overrightarrow{v\upsilon}) = (c(v), \beta)$ with $\alpha = \beta$ if and only if $c(u) < c(v)$.

**Proof of Theorem 2.** Let $G$ be an oriented graph and $V_1, \dots, V_k$ be the $k$ color classes of $V(G)$ induced by an acyclic $k$-coloring of $G$. By definition, $F_{i,j} = G[V_i, V_j]$ is a forest for $i, j \in [1, k]$, $i < j$ and there are $\frac{k(k-1)}{2}$ such forests; moreover, consider the $l = \lfloor \frac{k}{2} \rfloor$ forests $F_{1,2}, F_{3,4}, \dots, F_{2l-1,2l}$ (these forests do not share any vertex). We say that these $l$ forests are of type 1 while the remaining ones are of type 2. Then, we define an oriented arc-coloring $f_{i,j}$ for each forest $F_{i,j}$ as follows. If $F_{i,j}$ is of type 1, let $f_{i,j}$ be any oriented 3-arc-coloring given
by Lemma 3. If $F_{i,j}$ is of type 2, let $f_{i,j}$ be any oriented 4-arc-coloring given by Lemma 4.

Recall that each $\overrightarrow{uv} \in A(G)$ belongs to a unique forest $F_{i,j}$, $i, j \in [1, k]$, $i < j$. We now define the following mapping $f$ on $A(G)$:

$$ \forall \overrightarrow{uv} \in F_{i,j}, f(\overrightarrow{uv}) = (x, i, j) \quad \text{where} \quad x = f_{i,j}(\overrightarrow{uv}). $$

We shall prove that $f$ is an oriented arc-coloring of $G$. We first have to check that any pair of consecutive arcs $\overrightarrow{uv}$ and $\overrightarrow{vw}$ get distinct colors. If $\overrightarrow{uv}$ and $\overrightarrow{vw}$ belong to two distinct forests, say $\overrightarrow{uv} \in F_{i,j}$ and $\overrightarrow{vw} \in F_{j,k}$, then $f(\overrightarrow{uv}) = (x, i, j) \neq (y, j, k) = f(\overrightarrow{vw})$ for any $x, y$ since $i \neq k$. Now if $\overrightarrow{uv}, \overrightarrow{vw} \in F_{i,j}$, then $f(\overrightarrow{uv}) = (f_{i,j}(\overrightarrow{uv}), i, j) \neq (f_{i,j}(\overrightarrow{vw}), i, j) = f(\overrightarrow{vw})$ since $f_{i,j}$ is an oriented arc-coloring. Therefore, if $f$ is not an oriented arc-coloring of $G$, there are four arcs $\overrightarrow{uv}, \overrightarrow{vw}, \overrightarrow{xy}, \overrightarrow{yz}$ of $G$ with $f(\overrightarrow{uv}) = f(\overrightarrow{yz})$ and $f(\overrightarrow{vw}) = f(\overrightarrow{xy})$. Since any $f_{i,j}$ is an oriented arc-coloring, the arcs $\overrightarrow{uv}, \overrightarrow{vw}, \overrightarrow{xy}, \overrightarrow{yz}$ does not belong to the same forest and then $\overrightarrow{uv}, \overrightarrow{yz} \in F_{i,j}$ and $\overrightarrow{vw}, \overrightarrow{xy} \in F_{j,k}$, $i \neq k$. Since two forests of type 1 do not share any vertex, we assume w.l.o.g. that $F_{i,j}$ is of type 2. Suppose that $f(\overrightarrow{uv}) = f(\overrightarrow{yz}) = ((i, p), i, j)$ (resp. $((j, p), i, j)$) for some $p \in \{0, 1\}$. This implies that $y \in V_i$ (resp. $v \in V_i$). Then, since $f(\overrightarrow{vw}) = f(\overrightarrow{xy}) = (r, j, k)$ for some $r$, the vertex $y$ (resp. $v$) belongs either to $V_j$ or to $V_k$. This is a contradiction since $i \neq j \neq k \neq i$. This coloring uses at most $2k(k-1) - \lfloor \frac{k}{2} \rfloor$ colors. That completes the proof.

In order to study the relevance of the bound given by Theorem 2, we now construct graphs with bounded acyclic chromatic number and high oriented chromatic index.

The notion of *oriented k-tree* can be defined as follows: a tournament $T_k$ with $k$ vertices is an oriented k-tree; if $G$ is an oriented k-tree then the graph $G'$ obtained from $G$ by adding a new vertex $v$ linked to every vertex of a k-clique subgraph of $G$ is a k-tree, and there are no further k-trees. A subgraph of an oriented k-tree is called an oriented *partial k-tree*. We denote by $\mathcal{T}_k$ the class of oriented k-trees.

**Theorem 5.** $\chi'_o(\mathcal{T}_k) = \Omega(\frac{k^2}{\log k})$.

It is well known that the acyclic chromatic number of any k-tree is at most $k+1$. Indeed, at each step of the construction a k-tree, we color the new added vertex $v$ with a color distinct from those of the $k$ adjacent vertices of $v$; this coloring is clearly acyclic. Moreover, the clique of size $k+1$ is a k-tree and needs $k+1$ colors for any acyclic coloring. Therefore $\chi_o(\mathcal{T}_k) = k+1$, and we thus get:

**Corollary 6.** There exist oriented graphs with acyclic chromatic number $k$ and oriented chromatic index $\Omega(\frac{k^2}{\log k})$.

Recall that for a given vertex $v$ of a graph $G$ and a given oriented arc-coloring $f$ of $G$, $C_f^+(v)$ and $C_f^-(v)$ denote the outgoing color set of $v$ and the incoming color set of $v$, respectively.
**Proof of Theorem 5.** Let $h(k) = \chi'_o(\mathcal{T}_k)$. Every graph $G \in \mathcal{T}_k$ has an $h(k)$-arc-coloring $f$ such that $\forall v \in V(G), |C_f^+(v)| \le h(k) - h(k-1)$. Otherwise, we could construct a graph $G' \in \mathcal{T}_k$ with no $h(k)$-arc-coloring by adding to every vertex $v$ of $G$ a copy $H_v$ of a graph $H \in \mathcal{T}_{k-1}$ such that $\chi'_o(H) = h(k-1)$ and every arc $\bar{x}v$ for $x \in V(H_v)$. It is easy to check that the mapping $g$ defined by $g(v) = C_f^+(v)$ for every $v \in V(G)$ is an oriented vertex-coloring of $G$. Since $\chi_o(\mathcal{T}_k) \ge 2^{k+1} - 1$ [22], we obtain:

$$ 
\begin{aligned}
& \sum_{i=0}^{h(k)-h(k-1)} \binom{h(k)}{i} \ge 2^{k+1}-1, \\
& h(k)^{h(k)-h(k-1)} \ge 2^{k+1}-1, \\
& (h(k)-h(k-1)) \log h(k) \ge k, \\
& h(k) = \Omega\left(\frac{k^2}{\log k}\right)
\end{aligned}
$$

### 3. PLANAR GRAPHS

In this section, we consider planar graphs. In the next subsection, we give general bounds on the oriented chromatic index of planar graphs. In Subsection 3.B, we investigate the oriented chromatic index of planar graphs with high girth.

#### A. General Bounds

A celebrated result of Borodin [3] states that every planar graph has acyclic chromatic number at most five. Thus, from their previously mentioned result, Raspaud and Sopena [21] obtained that every oriented planar graph has oriented chromatic number at most 80, which is the best known upper bound for planar graphs up to now.

Sopena [22] constructed an oriented planar graph with oriented chromatic number 16. More recently, Marshall [16] showed that an oriented planar graph with oriented chromatic number at least 17 exists. The gap between the lower and the upper bound is large and seems to be very hard to reduce.

Concerning oriented arc-coloring of planar graphs, Theorem 2 and Borodin's result give the following upper bound:

**Corollary 7.** Let $G$ be a planar graph. Then $\chi'_o(G) \le 38$.

We give in the following a lower bound for the oriented chromatic index of the class of planar graphs: we construct a planar graph with oriented chromatic index at least 10.
<figure><img src="image_2.png" /><figcaption>FIGURE 1. The oriented outerplanar graph $O$ with oriented chromatic index 7.</figcaption></figure>

Pinlou and Sopena [20] proved that the oriented outerplanar graph $O$ depicted on Figure 1 has oriented chromatic index 7.

Let $H$ be the planar graph obtained by taking two copies of the graph $O$, namely $O_1$ and $O_2$, one new vertex $x$, and adding all arcs from the vertices of $O_1$ toward $x$ and all the arcs from $x$ toward the vertices of $O_2$ (see Fig. 2(a)). In the following, the vertex $x$ will be called the *joining vertex of $H$*. We denote by $A^{-}(H)$ (resp. $A^{+}(H)$) the set of incoming arcs to (resp. outgoing arcs from) the joining vertex of $H$.

**Lemma 8.** Any oriented 9-arc-coloring of $H$ uses seven colors to color $A(O_1)$, the same seven colors to color $A(O_2)$, the eighth color to color $A^{-}(H)$, and the ninth color to color $A^{+}(H)$.

**Proof.** We consider oriented 9-arc-colorings of $H$. Suppose that we use at most seven colors to color $A(O_1) \cup A^{-}(H)$, which would be best possible since $\chi_o'(O_1) = 7$.

* If exactly one color is used to color $A^{-}(H)$, then this color cannot appear on $A(O_1)$, a contradiction.

* If exactly two colors, say 1 and 2, are used to color $A^{-}(H)$, then these colors have to appear also on $A(O_1)$. So there exist arcs $\vec{uv}$ and $\vec{u'v'}$ in $O_1$, respectively, colored 1 and 2. Therefore, the arcs $\vec{vx}$ and $\vec{v'x}$ must be, respectively, colored 2 and 1, which is forbidden.

<figure><img src="image_3.png" /><figcaption>FIGURE 2. Graphs of Lemma 8 and Theorem 9. (a) The planar graph $H$; (b) The planar graph $H^*$.</figcaption></figure>
* If at least three colors are used to color $A^-(H)$, then there remain at most six colors to color $A(O_2)$, which contradicts $\chi_o'(O_2) = 7$.

We thus need at least eight colors to color $A(O_1) \cup A^-(H)$. This implies that there remains (at most) one color, say 9, to color $A^+(H)$. By a similar argument, we obtain that one color distinct from 9, say 8, has to be used to color $A^-(H)$. Seven colors distinct from 8 and 9 are needed to color $A^-(H)$ and $A^+(H)$.

Let $H^*$ be the graph obtained by taking two copies of the graph $H$, namely $H'$ and $H''$, and adding an arc from the joining vertex of $H'$ toward the joining vertex of $H''$ (see Fig. 2(b)). The joining vertex of $H'$ (resp. $H''$) is denoted by $x'$ (resp. $x''$).

**Theorem 9.** The graph $H^*$ has oriented chromatic index 10.

*Proof.* We suppose that $H^*$ admits an oriented 9-arc-coloring. By Lemma 8, we may assume w.l.o.g. that $A(O'_1)$ and $A(O'_2)$ use colors $1, 2, \dots, 7$, $A^-(H')$ uses color 8 and $A^+(H')$ uses color 9. The only available color for $x'x''$ is color 9. Now, colors 8 and 9 are obviously forbidden for $A^+(H'')$ and, from Lemma 8, we may assume w.l.o.g. that $A^+(H'')$ is colored with color 1; thus $A(O''_2)$ uses the seven colors $2, 3, \dots, 8$. Notice that the graph $O$ contains neither sources nor sinks. Therefore, there exists a color $c \in \{2, 3, \dots, 7\}$ such that two consecutive arcs in $O'_1$ are, respectively, colored with $c$ and 1. Now, the color $c$ is clearly used on $A(O''_2)$, which implies that $H''$ also contains two consecutive arcs, respectively, colored with 1 and $c$, which is a contradiction. The graph $H''$ has oriented chromatic index at least 10.

To show that $H^*$ has oriented chromatic index 10, we color $A(O'_1)$, $A(O'_2)$, $A(O''_1)$, and $A(O''_2)$ with the colors $1, 2, \dots, 7$, $A^-(H')$ and $A^-(H'')$ with color 8, $A^+(H')$ and $A^+(H'')$ with color 9, and $x'x''$ with color 10.

## B. Planar Graphs With High Girth

The girth of a planar graph is the size of a smallest cycle. Oriented chromatic number of planar graphs with large girth was widely studied [4–6,17]. In particular, Nešetřil et al. [17] proved that for every $g \ge 3$, there exists a planar graph $G$ with girth $g$ such that $\chi_o(G) \ge 5$.

We now prove that in case of oriented arc-coloring, this bound can be decreased to 4 for some high girth. Moreover, observe that for a directed cycle of length $l \ne 0$ (mod 3), any oriented arc-coloring needs at least 4 colors. Then, for any $g \ge 3$, consider the connected oriented graph $G_g$ obtained by taking two directed cycles sharing one arc, the first one of size $g$ and the second one of size $k \ge g$, $k \ne 0$ (mod 3). Clearly, $G_g$ has girth $g$ and oriented chromatic index 4, that shows the tightness of the bound we prove in the sequel.
<figure><img src="image_4.png" /><figcaption>FIGURE 3. The tournament $T_4$.</figcaption></figure>

Let $T_4$ be the tournament on four vertices depicted in Figure 3. We say that a $T_4$-arc-coloring $f$ of an oriented graph $G$ is *good* if

1. $\forall u \in V(G), C_f^+(u) \in \{\emptyset, \{1\}, \{2\}, \{3\}, \{4\}, \{2, 3\}, \{3, 4\}\}$,

2. $\forall u \in V(G), C_f^-(u) \in \{\emptyset, \{1\}, \{2\}, \{3\}, \{4\}, \{1, 2\}, \{2, 3\}\}$.

We first prove the following.

**Lemma 10.** Let $P = v_0v_1 \dots v_9v_{10}$ be an oriented 10-path of 2-vertices ($d(v_i) = 2$ for $1 \le i \le 9$). Then, any good $T_4$-arc-coloring of $P' = P \setminus \{v_2, \dots, v_8\}$ can be extended to a good $T_4$-arc-coloring of $P$.

*Proof.* Let $f'$ be a good $T_4$-arc-coloring of $P'$. To prove that the coloring $f'$ can be extended to $P$, we will use the auxiliary graph $H$ depicted in Figure 4 (the construction of $H$ is explained below).

The arc $v_0v_1$ of $P'$ is colored by $f'$: there exist eight possible cases, also called states, depending on the two possible orientations of $v_0v_1$ and the four possible colors. The eight vertices $s_1, s_2, s_3, s_4, s_{11}, s_{12}, s_{13}, s_{14}$ of $H$ correspond to these eight possible states. To construct the graph $H$, we consider all the possible cases of orientations and colorings. Suppose for instance that $\overrightarrow{v_0v_1} \in A(P)$, $f'(\overrightarrow{v_0v_1}) = 2$ (which corresponds to state $s_4$) and consider $v_1v_2$. If $\overrightarrow{v_1v_2} \in A(P)$, we can assign it colors 3 or 4, which corresponds to the state $s_5$. If $\overrightarrow{v_2v_1} \in A(P)$, we can assign it colors 1, 2, or 3 which corresponds to the state $s_{18}$. Proceeding in a similar way from any state, we eventually get the auxiliary graph $H$.

Finally, observe that every directed path of length nine in $H$ ends either in state $s_{10}$ or $s_{20}$. This means that we may obtain any possible color for $v_9v_{10}$, which

<figure><img src="image_5.png" /><figcaption>FIGURE 4. The auxiliary graph $H$ of Lemma 10.</figcaption></figure>
proves that every good $T_4$-arc-coloring $f'$ can be extended to a good $T_4$-arc-coloring of $P$.

**Theorem 11.** Let $G$ be a planar graph with girth $g \ge 46$. Then $G$ admits a good $T_4$-arc-coloring.

*Proof.* Consider a minimal counter-example $H$ to Theorem 11. We prove that $H$ contains neither a 1-vertex nor an oriented 10-path of 2-vertices.

* Suppose that $H$ contains a 1-vertex $u$, let $v$ be its neighbor and suppose that $\overrightarrow{uv} \in A(H)$. Let $H' = H \setminus u$. Due to the minimality of $H$, $H'$ admits a good $T_4$-arc-coloring $f$. Therefore, $C_f^+(v) \in \{\{1\}, \{2\}, \{3\}, \{4\}, \{2, 3\}, \{3, 4\}\}$. For each possible case, there exists a predecessor in $T_4$ we can use to extend $f$ to good $T_4$-arc-coloring of $H$. The proof of the case $\overrightarrow{vu} \in A(H)$ is similar.

* Suppose that $H$ contains a 10-path $uv_1v_2\dots v_9w$ of 2-vertices (therefore $d(v_i) = 2$ for all $i \in [1, 9]$) and let $H' = H \setminus \{v_2, v_3, \dots, v_8\}$. Due to the minimality of $H$, $H'$ admits a good $T_4$-arc-coloring $f$. Lemma 10 insures that $f$ can be extended to a good $T_4$-arc-coloring of $H$.

Nešětril et al. [17] proved that every planar graph $G$ of girth $g(G) \ge 5d+1$ contains either a 1-vertex or a $(d+1)$-path of 2-vertices. Therefore, since $g(H) \ge 46$, a counterexample to Theorem 11 does not exist. That completes the proof.

**4. GRAPHS WITH BOUNDED DEGREE**

Every oriented graph with maximum degree three has oriented chromatic number at most 11 [23]. Sopena [22] conjectured that the oriented chromatic number of *connected* oriented graphs with maximum degree three is at most 7. In case of oriented arc-coloring, Pinlou [19] recently proved that every oriented graph with maximum degree three has oriented chromatic index at most 7.

For the general case, Kostochka et al. [15] proved that every oriented graph with maximum degree $\Delta$ has oriented chromatic number at most $2\Delta^2 2^\Delta$ using a probabilistic argument. Therefore, for such a graph $G$ we also have $\chi_o'(G) \le 2\Delta^2 2^\Delta$. Alon et al. [1] proved that every graph with maximum degree $\Delta$ has acyclic chromatic number at most $O(\Delta^{4/3})$. Using Theorem 2, we thus get the better upper bound of $O(\Delta^{8/3})$ for the oriented chromatic index of oriented graphs with maximum degree $\Delta$.

We improve this latter bound and show the following.

**Theorem 12.** Let $G$ be an oriented graph with maximum degree $\Delta$. Then, $\chi_o'(G) \le 2(\lfloor \frac{\Delta^2}{2} \rfloor + \Delta)$.

*Proof.* Let $G^*$ be the undirected graph defined by $V(G^*) = V(G)$ and $uv \in E(G^*)$ if and only if $\overrightarrow{uv} \in A(G)$ or $\overrightarrow{vu} \in A(G)$ or there exists a vertex $t$ such that $\overrightarrow{ut}, \overrightarrow{tv} \in A(G)$. Gonçalves et al. [9] proved that such a graph $G^*$ is $(\lfloor \frac{\Delta^2}{2} \rfloor + \Delta)$-
degenerate (recall that a graph is $k$-degenerate if every subgraph contains a vertex of degree at most $k$). Let $p$ be a proper vertex-coloring of $G^*$ using at most $\lfloor \frac{\Delta^2}{2} \rfloor + \Delta + 1$ colors from $\{0, \dots, \lfloor \frac{\Delta^2}{2} \rfloor + \Delta\}$ obtained by a greedy coloring.

Now, let $c$ be the mapping from $A(G)$ to $\{1, \dots, \lfloor \frac{\Delta^2}{2} \rfloor + \Delta\} \times \{0, 1\}$ defined by
$$c(\vec{uv}) = (p(v), 0) \text{ if } p(u) < p(v) \text{ and } c(\vec{uv}) = (p(u), 1) \text{ if } p(u) > p(v).$$

We will show that $c$ is an arc-coloring of $G$.

Suppose first that $\vec{uv}$ and $\vec{vw}$ are two consecutive arcs of $G$ such that $c(\vec{uv}) = c(\vec{vw}) = (\alpha, i)$. If $i=0$ (resp. $i=1$) then $p(v) = p(w)$ (resp. $p(u) = p(v)$), a contradiction since $vw \in E(G^*)$ (resp. $uv \in E(G^*)$).

Suppose now that there are four arcs $\vec{uv}$, $\vec{vw}$, $\vec{xy}$, and $\vec{yz}$ of $G$ such that $c(\vec{uv}) = c(\vec{yz}) = (\alpha, i)$ and $c(\vec{vw}) = c(\vec{xy}) = (\beta, j)$. If $i = j = 0$, we get $\alpha = p(v) = p(z)$ and $p(v) < p(w)$ on one hand, $\beta = p(y) = p(w)$ and $p(w) = p(y) < p(z) = p(v)$ on the other hand, a contradiction. The case $i = j = 1$ leads to a contradiction in a similar way. Assume now that $i \neq j$ and w.l.o.g. that $i = 0$ and $j = 1$. Then we have $\alpha = p(v) = p(z)$ on one hand and $\beta = p(v) = p(x)$ on the other hand. Thus $p(z) = p(x)$, a contradiction since $xz \in E(G^*)$.

Therefore, the mapping $c$ is an arc-coloring of $G$ which uses at most $2(\lfloor \frac{\Delta^2}{2} \rfloor + \Delta)$ colors.

Concerning the lower bound, Pinlou [19] constructed a cubic graph with chromatic oriented index $6 = 2\Delta$. We are also able to construct an infinite family of oriented graphs with maximum degree $\Delta$ and oriented chromatic index $2\Delta - 1$. For that, let $n = 2\Delta - 1$ and consider the oriented bipartite graph $B_{n,n}$ defined by $V(B_{n,n}) = \{x_0, \dots, x_{n-1}, y_0, \dots, y_{n-1}\}$, $\overline{x_i y_i} \in A(B_{n,n})$ for all $0 \le i < n$ and $\overline{y_i x_k} \in A(B_{n,n})$ for all $0 \le i < n, 1 \le j < \Delta$ and $k = i + j \pmod n$. The graph $B_{n,n}$ is a $\Delta$-regular graph and any pair of arcs of $\{\overline{x_i y_i}, 0 \le i < n\}$ belongs to a directed 3-path and thus needs distinct colors.

# 5. ORIENTED CHROMATIC INDEX VERSUS ORIENTED CHROMATIC NUMBER

In this section, we show that the oriented chromatic number $\chi_o(G)$ of an oriented graph $G$ can be bounded in terms of the oriented chromatic index $\chi'_o(G)$.

Recall that we have $\chi'_o(G) \le \chi_o(G)$ for every oriented graph $G$ by Observation 1. This lower bound is tight since, for every $n$, we can construct a graph $G$ with $\chi'_o(G) = n = \chi_o(G)$. Let $TT_n$ be the transitive tournament on $n$ vertices with $V(TT_n) = \{v_0, v_1, \dots, v_{n-1}\}$ and $\overline{v_i v_j} \in A(TT_n)$ whenever $i \le j$. Then, let us consider $T_n$, the tournament on $n$ vertices obtained from $TT_n$ by reversing $\overline{v_0 v_{n-1}}$ (therefore $\overline{v_{n-1} v_0} \in A(T_n)$). Any pair of arcs of $S = \{\overline{v_i v_{i+1}} \in T_n, i \in [0, n-1]\}$ (subscripts are taken modulo $n$) belongs to a directed 3-path and thus all arcs in $S$ must get distinct colors. Therefore, $\chi'_o(T_n) = n = \chi_o(T_n)$.
<figure><img src="image_6.png" /><figcaption>FIGURE 5. The four non-isomorphic tournaments on four vertices. (a) $T_4^1$; (b) $T_4^2$; (c) $T_4^3$; (d) $T_4^4 = T_4$.</figcaption></figure>

We now focus on the upper bound on the oriented chromatic number in terms of oriented chromatic index. We first need the following definitions and the two next lemmas.

Let $G$ be an oriented graph and let $\mathcal{P}(G)$ be the power set of $V(G)$. We define the mapping $\mu_G$ as follows:

$$ \mu_G : \mathcal{P}(G) \to \mathcal{P}(G), \\ s \mapsto s \cup \bigcup_{v \in s} \Gamma_G^+(v). $$

For any oriented graph $G$, we then denote by $\mathcal{Q}(G)$ the set $\mathcal{Q}(G) = \{\mu_G(s), s \in \mathcal{P}(G)\}$ ($\mathcal{Q}(G)$ is therefore the codomain of $\mu_G$). Clearly, $\mathcal{Q}(G) \subseteq \mathcal{P}(G)$. For an element $s \in \mathcal{Q}(G)$, let $\bar{s} = \{v \in s; \Gamma_G^+(v) \subseteq s\}$ and $\underline{s} = \{v \in s; \Gamma_G^+(v) \not\subseteq s\}$; thus we have $s = \bar{s} \uplus \underline{s}$ (disjoint union).

For instance, consider the tournament $T_4$ depicted on Figure 5(d). We have $\mathcal{Q}(T_4) = \{\emptyset, \{1, 4\}, \{3, 4\}, \{1, 2, 3\}, \{1, 3, 4\}, \{2, 3, 4\}, \{1, 2, 3, 4\}\}$. Moreover, if we consider the element $s = \{1, 2, 3\}$ of $\mathcal{Q}(T_4)$, we have $\bar{s} = \{1\}$ and $\underline{s} = \{2, 3\}$.

**Lemma 13.** Let $G$ be an oriented graph with $\chi_o'(G) = k$ and let $T_k$ be an oriented graph on $k$ vertices such that $G$ admits a $T_k$-arc-coloring (i.e., $\text{LD}(G) \to T_k$). Then we have $\chi_o(G) \le |\mathcal{Q}(T_k)|$.

**Proof.** W.l.o.g., we shall consider that $T_k$ is a tournament (otherwise, we complete it).

Let $f$ be a homomorphism from $\text{LD}(G)$ to $T_k$; we define the mapping $g$ as follows:

$$ g : V(G) \to \mathcal{Q}(T_k), \\ v \mapsto \mu_{T_k}(C_f^+(v)). $$

We claim that $g$ is an oriented vertex-coloring of $G$. Let $\vec{uv} \in A(G)$ with $f(\vec{uv}) = a$. Since $a \in C_f^+(u)$, we have $a \in g(u)$ and $a \notin C_f^+(v)$; moreover, by definition of $f$, for every color $c \in C_f^+(v)$, $\vec{ca} \notin A(T_k)$, that is, $\vec{ac} \in A(T_k)$. Therefore $a \notin g(v)$ and $g$ is a proper vertex-coloring of $G$.
Now, if $g$ is not an oriented vertex-coloring of $G$, there exist two arcs $\vec{uv}$ and $\vec{xy}$ of $G$ with $g(u) = g(y)$ and $g(v) = g(x)$. Let $f(\vec{uv}) = a$ and $f(\vec{xy}) = b$. If $a \neq b$, since $T_k$ is a tournament, we may assume w.l.o.g. that $\vec{ab} \in A(T_k)$. Then, we have $b \in g(u)$ and therefore $b \in g(y)$. Now, if $a = b$, we have $b \in g(u)$ and therefore $b \in g(y)$. Thus, in both cases, $b \in g(y)$. Since $f$ is an oriented arc-coloring of $G$, $b \notin C_f^+(y)$. Hence, there exists a color $c \in C_f^+(y)$ such that $\vec{cb} \in A(T_k)$. Since $f(\vec{xy}) = b$, we also have $\vec{bc} \in A(T_k)$, that is a contradiction since $T_k$ is antisymmetric.

In particular, every oriented graph $G$ which admits a $T_4$-arc-coloring has oriented chromatic number at most 7 since $|Q(T_4)| = 7$ as observed above.

We now prove that the bound given by Lemma 13 is tight:

**Lemma 14.** For every tournament $T_k$ on $k$ vertices, there exists an oriented graph $G$ such that $\chi_o'(G) \le k$, $rmLD(G) \to T_k$ and $\chi_o(G) = |Q(T_k)|$.

*Proof.* Let $G$ be the digraph defined as follows: $V(G) = Q(T_k)$ and $\vec{xy} \in A(G)$ if and only if there exists $v \in V(T_k)$ such that $v \in \bar{x}$ and $v \notin y$.

We first have to check that $G$ is an oriented graph (without opposite arcs nor loops). Suppose to the contrary that $x, y \in V(G)$ are two vertices such that there exist $v_1$ and $v_2$ with $v_1 \in \bar{x}$, $v_1 \notin y$, $v_2 \in \bar{y}$ and $v_2 \notin x$. W.l.o.g. we assume that $\vec{v_1v_2} \in A(T_k)$: we obtain a contradiction since $v_2$ must belong to $x$. The graph $G$ is oriented.

We now show that any oriented vertex-coloring of $G$ needs $|Q(T_k)|$ colors (that is one distinct color for each vertex of $G$). Since any oriented vertex-coloring is a proper vertex-coloring, we just have to check that any pair of vertices $x$ and $y$ of $G$ which are not adjacent belongs to a directed 2-path. Let $x, y \in V(G)$ which are not adjacent; by construction we have $\bar{x} \subseteq y$ and $\bar{y} \subseteq x$. Moreover, $x \neq y$, and w.l.o.g. that implies that there exists $u \in V(T_k)$ such that $u \in \underline{x}$ and $u \notin y$. Furthermore, there exists $v \in \bar{x}$ such that $\vec{vu} \in A(T_k)$. Consider the vertex $z = \mu_{T_k}(\{u\})$ of $G$. We have $u \in \bar{z}$ and $v \notin z$. By construction, $\vec{xz}, \vec{zy} \in A$. Therefore $\chi_o(G) = |Q(T_k)|$.

Finally, we construct a mapping $f$ which is an oriented $k$-arc-coloring of $G$. Let $\vec{xy} \in A(G)$. Therefore, there exists $u$ such that $u \in \bar{x}$ and $u \notin y$. This implies that any $v_i \in \bar{y}$ is a successor of $u$ in $T_k$ (otherwise, $u$ would belong to $y$). Let $f: A(G) \to \{1, \dots, k\}$ be a mapping such that $f(\vec{xy}) = u$ for some $u \in \bar{x}$ and $u \notin y$: any arc outgoing from $y$ will then be colored by a successor of $u$ in $T_k$. Therefore, $LD(G) \to T_k$ and $\chi_o'(G) \le k$.

Note that the graph constructed in the previous theorem is the smallest possible since it has $|Q(T_k)|$ vertices and needs $|Q(T_k)|$ colors for any oriented vertex-coloring.

For instance, using the construction described in the previous proof, we are able to construct the graph $G$ depicted on Figure 6 which admits an oriented $T_4$-arc-coloring and has oriented chromatic number $|Q(T_4)| = 7$.

Let $\phi(k) = \max\{|Q(T_k)|, T_k$ is a tournament on $k$ vertices$\}$. From the two previous lemmas, we obtain the following upper bound:
<figure><img src="image_7.png" /><figcaption>FIGURE 6. An oriented graph with oriented chromatic index 4 and oriented chromatic number 7.</figcaption></figure>

**Theorem 15.** Let $G$ be an oriented graph with $\chi'_o(G) = k$. Then, $\chi_o(G) \le \phi(k)$. Moreover, this bound is tight.

*Proof.* Since $\chi'_o(G) = k$, there exists a tournament $T_k$ on $k$ vertices such that $G$ admits a $T_k$-arc-coloring. By Lemma 13, we have $\chi_o(G) \le |Q(T_k)|$, and therefore, $\chi_o(G) \le \phi(k)$.

Now, let $T_k^{\max}$ be a tournament on $k$ vertices such that $\phi(k) = |Q(T_k^{\max})|$. By Lemma 14, there exists an oriented graph $G$ such that $\chi_o(G) = |Q(T_k^{\max})| = \phi(k)$.

For instance, we can easily check for the four tournaments on four vertices depicted on Figure 5 that we have $|Q(T_4^1)| = 5$, $|Q(T_4^2)| = 6$, $|Q(T_4^3)| = 6$ and $|Q(T_4)| = 7$. We thus have $\phi(4) = 7$ and therefore any oriented graph with oriented chromatic index at most 4 has an oriented chromatic number at most 7.

The following theorem provides exact values of $\phi(k)$ for $k \le 9$ and estimates for $k \ge 10$.

**Theorem 16.**

* $\phi(0) = 1, \phi(1) = 2, \phi(2) = 3, \phi(3) = 5, \phi(4) = 7, \phi(5) = 12, \phi(6) = 15, \phi(7) = 25, \phi(8) = 31, \phi(9) = 51$;

* $\alpha 2^{\frac{k}{2}} - 1 \le \phi(k) \le (\lfloor \frac{k}{2} \rfloor + 2) 2^{\lfloor \frac{k-1}{2} \rfloor}$ for $k \ge 10$, where $\alpha = 2$ if $k$ is even and $\alpha = \frac{13}{4\sqrt{2}}$ if $k$ is odd.

To prove Theorem 16, we need the following lemma and the two following properties.

**Lemma 17.** Let $G$ be an oriented graph such that $\chi'_o(G) = p$ and $\chi_o(G) = q$. Then there exists a graph $H$ such that $\chi'_o(H) = p + 2$ and $\chi_o(H) = 2q + 1$.
<figure><img src="image_8.png" /><figcaption>FIGURE 7. The graph *H* of Lemma 17.</figcaption></figure>

**Proof.** Let $H$ be the oriented graph obtained by taking two disjoint copies of $G$ (denoted by $G_1$ and $G_2$) and a new vertex $z$ and adding all the arcs from the vertices of $G_1$ toward $z$ and all the arcs from $z$ toward the vertices of $G_2$ (see Fig. 7).

Since every pair of vertices $(v_1, v_2) \in V(G_1) \times V(G_2)$ belongs to a directed 2-path in $H$, we get $\chi_o(H) = 2q + 1$.

Now, let $A_1 = A(G_1)$, $A_2 = A(G_2)$, $A_- = \{\vec{uv} \in A(H), v = z\}$, $A_+ = \{\vec{uv} \in A(H), u = z\}$; therefore $A(H) = A_1 \uplus A_2 \uplus A_- \uplus A_+$. Let $g: A(G) \to \{1, \dots, p\}$ be an oriented $p$-arc-coloring of $G$ and let us then define the following mapping $h: A(H) \to \{1, \dots, p+2\}$ as follows:

$$h(\vec{uv}) = \begin{cases} g(\vec{uv}) & \text{if } \vec{uv} \in A_1 \cup A_2, \\ p+1 & \text{if } \vec{uv} \in A_-, \\ p+2 & \text{if } \vec{uv} \in A_+ \end{cases}$$

The mapping $h$ is an oriented $(p+2)$-arc-coloring of $H$ and thus $\chi'_o(H) \le p+2$. Moreover, as in the proof of Lemma 8, it is not difficult to check that $\chi'_o(H) = p+2$.

For an oriented graph $G$, we denote by $G^R$ the reverse graph of $G$, that is the graph obtained from $G$ by reversing every arc of $G$. Then, since $G^R \to H^R$ whenever $G \to H$, we clearly have:

**Observation 18.**

1. If $\chi_o(G) = k$ with $G \to T_k$, then $\chi_o(G^R) = k$ with $G^R \to T_k^R$;

2. If $\chi'_o(G) = k$ with $\mathrm{LD}(G) \to T_k$, then $\chi'_o(G^R) = k$ with $\mathrm{LD}(G^R) \to T_k^R$.

**Proof of Theorem 16.** For $k \le 9$, we used a computer to determine the values of $\phi(k)$.

For $k \ge 10$, by Lemma 17, we have $\phi(k+2) \ge 2\phi(k)+1$, which implies lower bounds of $\phi(k)$.

Now, we prove that $\phi(k) \le (\lfloor \frac{k}{2} \rfloor + 2)2^{\lfloor \frac{k-1}{2} \rfloor}$ for $k \ge 10$. By Theorem 15, there exists a graph $G$ with $\chi'_o(G) = k$ and $\chi_o(G) = \phi(k)$; therefore it is enough to show that $\chi_o(G) \le (\lfloor \frac{k}{2} \rfloor + 2)2^{\lfloor \frac{k-1}{2} \rfloor}$. Let $T_k$ be a tournament on $k$ vertices such that $\mathrm{LD}(G) \to T_k$. We order the vertices $v_1, v_2, \dots, v_k$ of $T_k$ in such a way that $d^+(v_i) \le d^+(v_j)$ for $i < j$. We first suppose that $d^+(v_i) \ge \lfloor \frac{k-1}{2} \rfloor$ for all $\lfloor \frac{k+1}{2} \rfloor \le i \le k$. Let $\mathcal{P}_i = \{s \subseteq \{v_1, v_2, \dots, v_i\}, v_i \in s\}$ and $\mathcal{Q}_i = \{\mu_{T_k}(s), s \in \mathcal{P}_i\}$. We then
have $\mathcal{P}(T_k) = \emptyset \cup \bigcup_{i=1}^n \mathcal{P}_i$ and therefore $\mathcal{Q}(T_k) \subseteq \emptyset \cup \bigcup_{i=1}^n \mathcal{Q}_i$. On one hand, since $|\mathcal{P}_i| = 2^{i-1}$, we have $|\mathcal{Q}_i| \le 2^{i-1}$. On the other hand, since each element of $\mathcal{Q}_i$ contains $v_i$ together with its successors in $T_k$, we have $|\mathcal{Q}_i| \le 2^{k-d^+(v_i)-1}$. We thus have

$$
\begin{align*}
|\mathcal{Q}(T_k)| &\le 1 + \sum_{i=1}^k |\mathcal{Q}_i| \\
&\le 1 + \sum_{i=1}^k \min\{2^{i-1}, 2^{k-d^+(v_i)-1}\} \\
&\le 1 + \sum_{i=1}^k 2^{i-1} + \sum_{i=\left\lfloor \frac{k}{2} \right\rfloor}^k 2^{k-d^+(v_i)-1} \\
&\le 1 + \sum_{i=1}^k 2^{i-1} + \sum_{i=\left\lceil \frac{k+1}{2} \right\rceil}^k 2^{k-\left\lceil \frac{k-1}{2} \right\rceil-1} \\
&\le 1 + 2\left\lfloor \frac{k}{2} \right\rfloor - 1 + \left\lceil \frac{k}{2} \right\rceil 2^{k-\left\lceil \frac{k-1}{2} \right\rceil-1} \\
&\le 2\left\lfloor \frac{k}{2} \right\rfloor + \left\lceil \frac{k}{2} \right\rceil 2^{\left\lfloor \frac{k-1}{2} \right\rfloor} \\
&\le \left(\left\lfloor \frac{k}{2} \right\rfloor + 2\right) 2^{\left\lfloor \frac{k-1}{2} \right\rfloor}
\end{align*}
$$

Therefore, $\chi_o(G) \le (\lfloor \frac{k}{2} \rfloor + 2)2^{\lfloor \frac{k-1}{2} \rfloor}$.

Now, suppose that $d^+(v_i) < \lfloor \frac{k-1}{2} \rfloor$ for some $i \ge \lfloor \frac{k}{2} \rfloor$. In this case, let us consider $T_k^R$. We have $d^+(v_i) \ge \lfloor \frac{k-1}{2} \rfloor$ for all $1 \le i \le \lfloor \frac{k}{2} \rfloor$. Using the previous argument, we get that $|\mathcal{Q}(T_k^R)| \le (\lfloor \frac{k}{2} \rfloor + 2)2^{\lfloor \frac{k-1}{2} \rfloor}$. By Observation 18(2), we have $\chi_o'(G^R) = k$ and $\text{LD}(G^R) \to T_k^R$. Therefore, $\chi_o(G^R) \le (\lfloor \frac{k}{2} \rfloor + 2)2^{\lfloor \frac{k-1}{2} \rfloor}$ and by Observation 18(1) $\chi_o(G) \le (\lfloor \frac{k}{2} \rfloor + 2)2^{\lfloor \frac{k-1}{2} \rfloor}$.

We thus have $\phi(k) \le (\lfloor \frac{k}{2} \rfloor + 2)2^{\lfloor \frac{k-1}{2} \rfloor}$ for all $k \ge 10$.

# 6. NP-COMPLETENESS

Complexity results for the oriented chromatic number were established recently. Klostermeyer and MacGillivray [14] have shown that given an oriented graph $G$, deciding whether $\chi_o(G) \le k$ is polynomial time if $k \le 3$ and is NP-complete if
$k \ge 4$. Culus and Demange [8] extended the above result to the case of bipartite oriented graphs and circuit-free oriented graphs.

In this section, we determine the complexity of deciding whether the oriented chromatic index of a given oriented graph is at most a fixed positive integer. Since the oriented chromatic index of an oriented graph $G$ is the oriented chromatic number of its line digraph $LD(G)$, the result we provide below is then an extension of Klostermeyer and MacGillivray's result to the case of line digraphs.

**Theorem 19.** *Given an oriented graph $G$, deciding whether $\chi'_o(G) \le k$ is polynomial time if $k \le 3$ and NP-complete if $k \ge 4$.*

*Proof.* The case $k \le 3$ directly follows from Klostermeyer and MacGillivray's result since $\chi'_o(G) = \chi_o(LD(G))$ and $LD(G)$ can be constructed from $G$ in polynomial time.

We show that the case $k=4$ is NP-complete using a reduction from 3-COLORABILITY. We construct the oriented graph $G'$ from an undirected graph $G$ as follows. For every vertex $v$ of $G$, we put an arc $v'$ in $G'$. For every edge $xy$ in $G$, we add a directed 4-path of 2-vertices joining the head of $x'$ to the tail of $y'$, and another 4-path of 2-vertices joining the head of $y'$ to the tail of $x'$. Hence, $G'$ contains 10-circuits (i.e., a directed cycles on ten vertices) induced by the edges of $G$: such a 10-circuit induced by the edge $xy$ is denoted by $C_{x,y}$. Thus, any oriented arc-coloring needs at least four colors. Therefore, we have $\chi'_o(G') \le 4$ if and only if $LD(G')$ has a homomorphism to the tournament $T_4$ depicted in Figure 3 ($T_4$ is the only tournament on four vertices containing a 4-circuit). Notice that, for any edge $xy$ of $G$, the arcs $x'$ and $y'$ are opposite arcs on $C_{x,y}$. We easily check by a case study that for every pair of vertices $u$ and $v$ of $T_4$, there exists a 5-walk from $u$ to $v$ unless $u = v$, or $u = 3$ and $v = 2$. Therefore, any $T_4$-arc-coloring $h$ of $C_{x,y}$ is such that $h(x') \neq h(y')$ and that every couple of distinct colors can be obtained for $(h(x'), h(y'))$ except (2, 3) and (3, 2). If $c$ is a proper 3-vertex-coloring of $G$, then $G'$ admits a $T_4$-arc-coloring $h$ such that $h(v') = 1$ if $c(v) = 1$, $h(v') = 2$ if $c(v) = 2$, and $h(v') = 4$ if $c(v) = 3$. Conversely, if $G'$ admits a $T_4$-arc-coloring $h$, then the coloring $c$ of $G$ such that $c(v) = 1$ if $h(v') = 1$, $c(v) = 2$ if $h(v') = 2$ or $h(v') = 3$, and $c(v) = 3$ if $h(v') = 4$, is a proper 3-vertex-coloring.

We now consider the case $k \ge 4$, $k$ even. We consider the problem whether $\chi'_o(G) \le k$ restricted to oriented graphs $G$ containing neither sources nor sinks. This case is done by induction on $k$. Notice that the oriented graphs in the proof of the case $k=4$ contain neither sources nor sinks, so $k=4$ is our base case. We construct an oriented graph $G'$ without sources nor sinks from an oriented graph $G$ without sources nor sinks, such that $\chi'_o(G') = \chi'_o(G) + 2$. The graph $G'$ is obtained from $G$ by adding three vertices $v_1, v_2, v_3$, the arcs $\overrightarrow{v_1v_2}, \overrightarrow{v_2v_3}$, and the arcs $\overrightarrow{vv_1}, \overrightarrow{v_3v}$, for every vertex $v$ of $G$. Any oriented $k$-arc-coloring $f$ of $G$ can be extended to an oriented $(k+2)$-coloring of $G'$ as follows. The arcs $\overrightarrow{vv_1}$ (resp. $\overrightarrow{v_3v}$) get the same color as one of $C_f^+(v)$ (resp. $C_f^-(v)$) since $C_f^+(v) \neq \emptyset$ and $C_f^-(v) \neq \emptyset$. The arcs $\overrightarrow{v_1v_2}$ and $\overrightarrow{v_2v_3}$ get additional colors. Conversely, any oriented $k$-arc-coloring of $G'$ induces an oriented $(k-2)$-arc-coloring of $G$. To see this, notice that every arc
$\overrightarrow{xy}$ of $G$ is contained in the 5-circuit $\overrightarrow{xy}, \overrightarrow{yv_1}, \overrightarrow{v_1v_2}, \overrightarrow{v_2v_3}, \overrightarrow{v_3x}$, which implies that the color of $\overrightarrow{xy}$ is distinct from those of $\overrightarrow{v_1v_2}$ and $\overrightarrow{v_2v_3}$.

We finally consider the case $k \ge 4$, $k$ odd. We construct an oriented graph $G'$ from an oriented graph $G$ without sources nor sinks, such that $\chi_o'(G') = \chi_o'(G) + 1$. The graph $G'$ is obtained from $G$ by adding two vertices $v_1, v_2$, the arc $\overrightarrow{v_1v_2}$, and the arcs $\overrightarrow{vv_1}$, for every vertex $v$ of $G$. As above, we check that any oriented $k$-arc-coloring of $G$ can be extended to an oriented $(k+1)$-coloring of $G'$, any oriented $k$-arc-coloring of $G'$ induces an oriented $(k-1)$-arc-coloring of $G$.

# 7. DISCUSSION AND FURTHER WORK

In this article, we provided some bounds on the oriented chromatic index. In particular, we proved in Section 3 that every oriented planar graph has oriented chromatic index at most 38, and showed that this bound can be decreased to 4 when considering planar graphs with girth at least 46. It is known that planar graphs with girth at least 4 (resp. 5, 6, 7, 14) have oriented chromatic number at most 47 (resp. 19, 11, 7, 5) (see [4–6]). These bounds are also valid for the oriented chromatic index thanks to Observation 1. It would be interesting to obtain better bounds on the oriented chromatic index of these graph classes.

We also studied and bounded $\chi_o(G)$ in terms of $\chi_o'(G)$, $\chi_o$ in terms of $\chi_o(G)$, and $\chi_o'(G)$ in terms of $\chi_a(G)$. Kostochka et al. [15] proved that, for every oriented graph $G$ with $\chi_o(G) = k$, we have $\chi_a(G) \le k^2 + k^{3+\lfloor \log \log k \rfloor}$; this gives us a first bound for $\chi_a(G)$ in terms of $\chi_o'(G)$ using Theorem 16. So, it would also be interesting to improve this bound by a direct study.

# REFERENCES

[1] N. Alon, C. J. H. McDiarmid, and B. Reed, Acyclic coloring of graphs, Random Struct Algorithm 2(3) (1991), 277–288.

[2] S. Bessy, F. Havet, and E. Birmelé, Arc-chromatic number of digraphs in which each vertex has bounded outdegree or bounded indegree, J Graph Theory 53(4) (2006), 315–332.

[3] O. V. Borodin, On acyclic colorings of planar graphs, Discrete Math 25 (1979), 211–236.

[4] O. V. Borodin and A. O. Ivanova, An oriented 7-colouring of planar graphs with girth at least 7, Sib Electron Math Reports 2 (2005), 222–229.

[5] O. V. Borodin and A. O. Ivanova, An oriented colouring of planar graphs with girth at least 4, Sib Electron Math Reports 2 (2005), 239–249.

[6] O. V. Borodin, A. V. Kostochka, J. Nešetřil, A. Raspaud, and É. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math 206 (1999), 77–89.
[7] B. Courcelle, The monadic second order-logic of graphs VI: On several representations of graphs by relational structures, Discrete Appl Math 54 (1994), 117–149.

[8] J.-F. Culus and M. Demange, Oriented coloring: Complexity and approximation, In J. Wiedermann et al. (Editor), SOFSEM, Lecture Notes in Comput Sci 3831 (2006), 226–236.

[9] D. Gonçalves, M. A. Shalu, and A. Raspaud, On oriented labelling parameters, In M. Mukund K. G. Subramanian, K. Rangarajan (Editor), Formal Models, Languages and Applications, Vol. 66, Series in Machine Perception and artificial Intelligence, chapter 3, World Scientific, Singapore, 2005, pp. 34–45.

[10] B. Guiduli, On incidence coloring and star arboricity of graphs, Discrete Math 163 (1997), 275–278.

[11] C. C. Harner and R. C. Entringer, Arc colorings of digraphs, J Combin Theory B 13 (1972), 219–225.

[12] P. Hell and J. Nešetřil, Graphs and homomorphisms, Vol. 28, Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, UK, 2004.

[13] H. Kawai, N. Fujikake, and Y. Shibata, Factorization of de bruijn digraphs by cycle-rooted trees, Inform Process Lett 77(5–6) (2001), 269–275.

[14] W. F. Klostermeyer and G. MacGillivray, Homomorphisms and oriented colorings of equivalence classes of oriented graphs, Discrete Math 274(1–3) (2004), 161–172.

[15] A. V. Kostochka, É. Sopena, and X. Zhu, Acyclic and oriented chromatic numbers of graphs, J Graph Theory 24 (1997), 331–340.

[16] T. H. Marshall, Homomorphism bounds for oriented planar graphs, J Graph Theory JGT 55(3) (2007) 175–190.

[17] J. Nešetřil, A. Raspaud, and É. Sopena, Colorings and girth of oriented planar graphs, Discrete Math 165–166 (1997), 519–530.

[18] P. Ochem, Negative results on acyclic improper colorings, In Stefan Felsner (Editor), European Conference on Combinatorics, Graph Theory and Applications (EuroComb’05), Vol. AE, DMTCS Proceedings, pp. 357–362, Discrete Math Theoret Comput Sci, 2005.

[19] A. Pinlou, On oriented arc-coloring of subcubic graphs, Elect J Comb 13(1) (2006).

[20] A. Pinlou and É. Sopena, Oriented vertex and arc colorings of outerplanar graphs, Inform Process Lett 100(3) (2006), 97–104.

[21] A. Raspaud and É. Sopena, Good and semi-strong colorings of oriented planar graphs, Inform Process Lett 51(4) (1994), 171–174.

[22] É. Sopena, The chromatic number of oriented graphs, J Graph Theory 25 (1997), 191–205.
[23] É. Sopena, Oriented graph coloring, Discrete Math 229(1–3) (2001), 359–369.

[24] D. R. Wood, Acyclic, star and oriented colourings of graph subdivisions, Discrete Math Theoret Comput Sci 7(1) (2005), 37–50.