Julien Bensmail

Sandip Das

Soumen Nandi

Ayan Nandy

Théo Pierron

Swathy Prabhu

Sagnik Sen

Oriented Total-Coloring of Oriented Graphs $

Keywords: oriented coloring, oriented arc-coloring, total-coloring, oriented graph

A proper n-coloring of a graph G is an assignment of colors from {1, . . . , n} to its vertices such that no two adjacent vertices get assigned the same color. The chromatic number of G, denoted by χ(G), refers to the smallest n such that G admits a proper n-coloring. This notion naturally extends to edge-colorings (resp. total-colorings) when edges (resp. both vertices and edges) are to be colored, and this provides other parameters of G: its chromatic index χ (G) and its total chromatic number χ (G).

These coloring notions are among the most fundamental ones of the graph coloring theory. As such, they gave birth to hundreds of studies dedicated to several of their aspects, including generalizations to more general structures such as oriented graphs. They include notably the notions of oriented n-colorings and oriented n-arc-colorings, which stand as natural extensions of their undirected counterparts, and which have been receiving increasing attention.

Our goal is to introduce a missing piece in this line of work, namely the oriented counterparts of proper n-total-colorings and total chromatic number. We first define these notions and show that they share properties and connections with oriented (arc) colorings that are reminiscent of those shared by their undirected counterparts. We then focus on understanding the oriented total chromatic number of particular types of oriented graphs, such as oriented forests, cycles, and some planar graphs. Finally, we establish a full complexity dichotomy for the problem of determining whether an oriented graph is totally k-colorable.

Throughout this work, each of our results is compared to what is known regarding the oriented chromatic number and oriented chromatic index. We also disseminate some directions for further research on the oriented total chromatic number.

Introduction

In this article, we introduce and study a generalization of proper total-colorings of (undirected) graphs to oriented graphs. Previous work on related topics proved that there are usually several possible ways of generalizing coloring-related notions, and this still holds in the current context. Our main source of motivation for introducing proper total-colorings of oriented graphs the way we do, is that their connections with oriented colorings and oriented arc-colorings of oriented graphs are reminiscent of the connections between the more classical notions of proper total-colorings, proper colorings, and proper edge-colorings of graphs.

We assume that the reader is familiar with the most standard notions and terminology on graphs; for anything not defined here, we refer them to any monograph on the topic.

Definitions. Given a graph1 G, an orientation -→ G of G is obtained by assigning a direction to every edge joining any two vertices u and v, resulting in an arc either uv from u to v (v being an out-neighbor of u, u being an in-neighbor of v, and uv being in-coming to v and out-going from u), or vu from v to u (and vice versa). Such an orientation -→ G is also called an oriented graph with underlying graph G. Alternatively, an oriented graph is a directed graph without any directed cycle of length 1 or 2. For an oriented graph -→ G , we denote by V ( -→ G ) and A( -→ G ) its vertex and arc sets.

Oriented total-colorings. As mentioned earlier, there are multiple ways to generalize classical coloring notions from graphs to oriented graphs. The coloring notions for oriented graphs we investigate throughout this work are based on the following simple notion of elements flowing to each other, which, although not classical, provides a general framework encapsulating all these upcoming oriented coloring notions. Let uv and vw be two distinct arcs of an oriented graph. We say that the vertex u flows to the arc uv and to the vertex v, and that the arc uv flows to the vertex v and to the arc vw. Conversely, we say that the vertex w flows from the vertex v and from the arc vw, and that the arc vw flows from the vertex v and from the arc uv.

Through this notion of elements flowing to each other, we are now ready to recall and introduce the three main coloring notions to be investigated in this paper. Let us start with the new, most general, notion we introduce in this paper (see below for reasons why we introduce it in this precise way). Let -→ G be an oriented graph, and let n 1. An oriented n-total-coloring of

- → G is a function τ : V ( - → G ) ∪ A( - → G ) → {1, .
. . , n} satisfying the following conditions:

1. if a, b ∈ V ( - → G ) ∪ A( - → G )
are such that a flows to b, then τ (a) = τ (b); The oriented total chromatic number of -→ G , denoted by χ o ( -→ G ), is the minimum n such that -→ G admits an oriented n-total-coloring. Now, if, in the definition above, we restrict the domain of the function τ to V ( -→ G ), then what we get is exactly the definition of oriented n-colorings of oriented graphs [START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF]. To make it clear, note that an oriented coloring is a proper assignment of colors to the vertices (i.e., no two adjacent vertices get assigned the same color) such that if we focus on the vertices being assigned any pair of distinct colors i and j, then we have the property that all arcs joining such vertices always go the same direction, i.e., either from the vertices colored i to those colored j, or vice versa. Similarly, if we restrict the domain of τ to A( -→ G ), then we obtain exactly the definition of oriented n-arc-colorings of oriented graphs [START_REF] Ochem | On the oriented chromatic index of oriented graphs[END_REF]. Recall that the oriented chromatic number χ o ( -→ G ) of -→ G is the smallest n such that -→ G admits oriented n-colorings, while the oriented chromatic index χ o ( -→ G ) of -→ G is the smallest n such that -→ G admits oriented n-arc-colorings. Thus, as suggested earlier, our definition of oriented total-colorings actually encapsulates that of oriented colorings and oriented arc-colorings, which can be seen as a combination of the two. This will be made even more apparent through later connections, which we postpone to Section 2 for the sake of keeping the current introduction short.

2. if a, b, c, d ∈ V ( - → G ) ∪ A( - → G )
Related work. Recall that oriented colorings were introduced as early as in the 1990s, as they emerged as a generalization of proper colorings of graphs to oriented graphs in the famous series of works led by Courcelle on monadic second order logic (see e.g. [START_REF] Courcelle | The monadic second order logic of graphs vi: On several representations of graphs by relational structures[END_REF]). Soon after, the work [START_REF] Raspaud | Good and semi-strong colorings of oriented planar graphs[END_REF], dedicated to the topic, generated a lot of interest into this new area which, since then, has been intensively explored by several authors, see [START_REF] Borodin | On deeply critical oriented graphs[END_REF][START_REF] Borodin | Homomorphisms from sparse graphs with large girth[END_REF][START_REF] Borodin | On universal graphs for planar oriented graphs of a given girth[END_REF][START_REF] Borodin | On the maximum average degree and the oriented chromatic number of a graph[END_REF][START_REF] Kostochka | Acyclic and oriented chromatic numbers of graphs[END_REF][START_REF] Marshall | Homomorphism bounds for oriented planar graphs[END_REF][START_REF] Borodin | On acyclic colorings of planar graphs[END_REF][START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF]. This all opened the way for many later works generalizing other related classical coloring notions to the realm of oriented graphs, such as the clique number [START_REF] Nandy | Outerplanar and planar oriented cliques[END_REF], the chromatic index [START_REF] Ochem | On the oriented chromatic index of oriented graphs[END_REF], the achromatic number [START_REF] Sopena | Complete oriented colourings and the oriented achromatic number[END_REF], and the list chromatic number [START_REF] Tuza | Oriented list colorings of graphs[END_REF], to name a few. In a sense, our main intention in this work takes place in that line of research, since, as far as we are aware, no attempt to generalize proper total-colorings to oriented graphs has been made to date.

Organization of the paper. We start off in Section 2 by giving an alternative definition of oriented colorings using the so-called graph homomorphisms, which also leads to a better illustration of how the three kinds of colorings relate to each other. As a warm up, we then investigate oriented graphs with small oriented total chromatic number, as well as easy classes of oriented graphs (namely oriented forests and cycles) in Section 3. We then go more general in Section 4, by looking for connections between the oriented total chromatic number and other graph chromatic parameters. Next, in Section 5, we prove that determining whether a given oriented graph

- → G verifies χ o ( - → G ) =
k is polynomial-time solvable for every k 5 and NP-complete for every k 6. Lastly, in Section 6, we focus on the case where the underlying graph is planar, with possibly some restrictions such as having a large girth or being outerplanar.

As mentioned earlier, oriented (arc) colorings already received an enormous amount of attention over the years, as attested notably by the survey [START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF]. As a result, many directions can be taken to study the total version we introduce. We disseminate some throughout the paper, and summarize them in the concluding Section 7.

Preliminaries

Colorings as graph homomorphisms

A common way to study oriented colorings is through the lens of homomorphisms of oriented graphs, a notion we recall now. A homomorphism of an oriented graph

- → G to an oriented graph - → H is a vertex-mapping f : V ( - → G ) → V ( - → H ) such that for every arc uv of - → G , the arc f (u)f (v) is also in - → H . If - → G admits a homomorphism f to - → H , then we denote it by f : - → G → - → H , or more generally by - → G → - → H . Note that a homomorphism of - → G to - → H provides a coloring (which we call an - → H -coloring) of the vertices of - → G with colors from V ( - → H ).
Actually, it can be checked from the definition that any These observations extend to oriented arc-colorings and oriented total-colorings through the following transformations (see Figure 1). Recall that a k-path in a graph is a path of length k, and that an orientation of a k-path is a directed k-path if its arcs are oriented from one end to the other. Similarly, a k-cycle C k is a cycle of length k, and a directed k-cycle -→ C k is an orientation of a k-cycle in which all arcs follow the same direction.

- → H -coloring of - → G is an oriented coloring. In particular, any oriented n-coloring of - → G is an - → H -coloring for some oriented graph - → H with |V ( - → H )| = n,
( - → G ) of - → G is the smallest n such that - → G admits an - →
H -total-coloring for an oriented graph -→ H of order n. It is worth reminding that these connections between the three coloring notions are reminiscent of similar connections that exist between their undirected counterparts. Indeed, proper n-colorings of G can also be expressed as homomorphisms of G to graphs H of order n, where, recall, a homomorphism f :

V (G) → V (H) of G to H is a vertex-mapping of V (G) to V (H)
that preserves all edges. In turn, proper n-edge-colorings and proper n-total-colorings of G can be expressed as homomorphisms of graphs obtained from G to graphs H of order n. Namely, from G, one can obtain its subdivision graph S(G) by replacing every edge uv by a 2-path ue uv v, its total graph T (G) by adding edges between vertices at distance 2 in S(G), and its line graph L(G) by considering the subgraph of S(G) induced by the e uv 's. As previously, proper n-edge-colorings and proper n-total-colorings can now be seen as homomorphisms of L(G) and T (G) to graphs of order n, respectively.

Using this alternate definition, we can state the following property, whose proof is an easy adaptation of the corresponding undirected statement.

Proposition 2.1. If - → G and - → H are two oriented graphs such that - → G → - → H , then χ o ( - → G ) χ o ( - → H ).

Cliques in oriented graphs

The clique number ω(G) of a graph G, defined as the size of a largest clique (or complete subgraph) in G, stands as an obvious lower bound for the chromatic number, i.e., ω(G) χ(G) always holds. This notion was extended to oriented graphs as follows. Let -→ G be an oriented graph. We say that a subset R of vertices of -→ G is a relative oriented clique if the vertices of R must all be assigned distinct colors in every oriented coloring of -→ G . As will be made apparent in upcoming Lemma 2.

( - → G ) ω r ( - → G ) χ o ( - → G )
always holds, which generalized the aforementioned naive lower bound.

In this work, we will only need the following characterization of relative oriented cliques. For more details on all these notions, we refer the interested reader to e.g. [START_REF] Sen | A contribution to the theory of graph homomorphisms and colorings[END_REF].

Lemma 2.2 ([11]). For an oriented graph

- → G , a subset R ⊆ V ( - → G
) is a relative oriented clique if and only if every two of its vertices are either adjacent or joined by a directed 2-path (in -→ G ).

Oriented graphs of small oriented total chromatic number

In this section, we provide a description of all oriented graphs with oriented total chromatic number at most 5. We handle the totally 5-chromatic oriented graphs for later, and start with the totally 4-colorable ones.

Recall that, in an oriented graph, a source is a vertex incident to no in-coming arcs, while a sink is a vertex incident to no out-going arcs. Theorem 3.1. For every oriented graph -→ G , we have the following:

1. χ o ( - → G ) 1 if and only if V ( - → G ) is an independent set. 2. χ o ( - → G ) / ∈ {2, 4}. 3. χ o ( - → G ) 3 if
( - → G ) χ o ( - → P ) = 5.
Otherwise, -→ G does not contain any directed 2-path. In particular, every vertex is either a source or a sink, and assigning color 1 to the sources and isolated vertices, color 2 to the arcs, and color 3 to the sinks yields an oriented 3-total-coloring of -→ G . Note that the previous arguments imply the second item of the statement holds.

Note that Theorem 3.1 indicates that some values cannot appear as the oriented total chromatic number of any oriented graph. As a byproduct of the proof of Theorem 5.1 (and more precisely Lemma 5.3), we know that 2 and 4 are actually the only such values.

We now focus on totally 5-chromatic oriented graphs. We first need the following definitions. Let -→ G be an oriented graph and γ = v 0 • • • v k v 0 be a closed walk in the underlying graph G. For every i ∈ {0, . . . , k}, we say that v i v i+1 (where, by convention,

v k+1 = v 0 ) is a forward edge if v i v i+1 ∈ A( - → G
) and a backward edge otherwise. Note that some edges of G can be counted as forward and backward if γ goes several times through them. The signature of γ is the absolute value of the difference between the number of forward and backward edges of γ. • -→ G does not contain a directed 3-path.

• The signature of every closed walk of G is a multiple of 5.

We say that -→ G is consistent if it fulfils one of the two conditions. Note that it is equivalent to require that 5 divides the signature of every cycle of G. Proof of Theorem 3.2. Assume that there exists an oriented 5-total-coloring f of -→ G and that -→ G contains a directed 3-path wxyz. Without loss of generality, in T ( -→ G ) we may assume that w, e wx , x, e xy , y, e yz , z have colors 1 to 5 in this order. Moreover, we must have f (e yz ) = f (w) = 1 and f (z) = f (e wx ) = 2. In particular, f is actually a -→ T 5 -coloring of T ( -→ G ) where -→ T 5 is depicted on Figure 2. Also, if uv is an arc, then f (v) -f (u) = 2 mod 5. By summing this relation for each edge of a closed walk in G, we get 2σ = 0 mod 5 where σ is the signature of the closed walk. Therefore, σ is a multiple of 5 and -→ G is consistent. Conversely, let -→ G be a consistent oriented graph. If -→ G does not contain any directed 3-path, then we color each source with 1, each sink with 5, and the remaining vertices (which are neighbors of precisely one source and one sink) with 3. Now each arc uv gets color cu+cv 2 where c u and c v are the colors of u and v. This yields an oriented 5-total-coloring of -→ G (and more precisely a homomorphism from T ( -→ G ) to the only orientation of K 5 without directed cycle). We may thus assume that -→ G contains a directed 3-path and that the signature of every closed walk of G is a multiple of 5. We will construct a -→ T 5 -total-coloring of -→ G in two steps: first, we color the vertices with colors from {1, . . . , 5} such that, for every arc xy, if x gets color i then y gets color i + 2 mod 5; second, we extend this coloring to arcs.

For the first step, we choose any vertex v of -→ G arbitrarily and color it with 1. Then, for every other vertex w of -→ G , we consider a path

γ = v 0 • • • v k from v 0 = v to v k = w in G (
which exists, since G can be assumed to be connected). We denote by f γ the number of forward arcs

v i v i+1 ∈ A( - → G ) and by b γ the number of backward arcs v i+1 v i ∈ A( - → G ).
We color w with 1 + 2(f γ -b γ ) mod 5. Note that this is independent of the choice of γ. Indeed, if γ is another such path, then following γ and then γ in reverse order yields a closed walk in G, whose signature is

|f γ -b γ -(f γ -b γ )|. Since - → G is consistent, we get that 1 + 2(f γ -b γ ) = 1 + 2(f γ -b γ ) mod 5.
Therefore, this oriented coloring is well defined. Now for each arc xy of -→ G , we know that if x has color i, then y is colored with i + 2 mod 5. We color xy with i + 1 mod 5. This eventually yields a

-→ T 5 -total-coloring of - → G .
We now apply these results to provide a full classification of oriented forests and cycles with respect to their oriented total chromatic number.

Recall, see e.g. [START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF], that

χ o ( - → F ) χ o ( - → F ) 3 for every oriented forest - → F .
Regarding the oriented total chromatic number, earlier Theorems 3.1 and 3.2 directly yield the following.

Theorem 3.3. If - →
F is an oriented forest, then:

1. χ o ( - → F ) 1 if and only if V ( - → F ) is an independent set; 2. χ o ( - → F ) 3 if and only if - → F contains no directed 2-path; 3. χ o ( - → F ) = 5 otherwise, i.e., if and only if - → F contains at least one directed 2-path.
Recall, see [START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF], that

χ o ( - → C ) χ o ( - → C ) 5 for every oriented cycle - → C (actually, χ o ( - → C ) = χ o ( - → C ) = 5 only for - → C being the directed 5-cycle).
Regarding the oriented total chromatic number, we prove the following.

Theorem 3.4. If - →
C is an oriented cycle, then:

1. χ o ( - → C ) 3 if and only if - → C contains no directed 2-path; 2. χ o ( - → C ) 5 if and only if - → C is consistent; 3. χ o ( - → C ) 6 if and only if - → C is neither the directed 4-cycle -→ C 4 nor the directed 7-cycle -→ C 7 ; 4. χ o ( - → C ) = 7 if and only if - → C = -→ C 7 ; 5. χ o ( - → C ) = 8 if and only if - → C = -→ C 4 .
Proof. The first item follows from Theorem 3.1, while the second item follows from Theorem 3.2.

The fifth item follows from the fact that T ( -→ C 4 ) is an absolute oriented clique on 8 vertices. We now show that χ o ( -→ C 7 ) = 7. An oriented 7-total-coloring of -→ C 7 is given on Figure 3(e). Moreover, observe that T ( -→ C 7 ) has exactly 14 vertices, and that, for any three of them, at least two are adjacent or linked by a directed 2-path. Therefore, in any oriented total-coloring of -→ C 7 , each color class has size at most 2. Hence χ o ( -→ C 7 ) 14 2 = 7, which proves that the oriented total chromatic number of -→ C 7 is exactly 7.

It now remains to show that every oriented cycle other than -→ C 4 and -→ C 7 has an oriented 6-totalcoloring. Let -→ C be an oriented cycle which is not directed. In particular, -→ C contains a source u and a sink v. Let us denote by -→ P and -→ P the two arc-disjoint oriented paths with ends u and v. By Theorem 3.3, we know that there exist homomorphisms f :

T ( - → P ) → -→ T 5 and f : T ( -→ P ) → -→ T 5 . Furthermore, since -→ T 5 is vertex-transitive, we can assume that f (u) = 1 = f (u)
. Now, to obtain an oriented 6-total-coloring of -→ C , we can just assign color 6 to v and color the other vertices of T ( -→ C ) with their color from f or f . We are left with the case of directed cycles -→ C n with n / ∈ {4, 7}. Note that we can write n = 3a + 5b for some non-negative integers a and b. Moreover, Figures 3(a) and (c) handle the cases n ∈ {3, 5}, and, hence, we may assume that a + b 2. We partition the arcs of -→ C n into a directed 3-paths and b directed 5-paths, each one having its ends coinciding with those of other directed paths. We now color each directed path using one of the following two ways.

Observation 3.5. For every directed 3-path v 0 v 1 v 2 v 3 , setting τ (v i ) = 2i+1 mod 6 and τ (v i v i+1 ) = 2i + 2 mod 6 for every i yields an oriented 6-total-coloring satisfying τ (v 0 ) = τ (v 3 ) = 1. Observation 3.6. For every directed 5-path v 0 v 1 v 2 v 3 v 4 v 5 , setting τ (v i ) = 2i + 1 mod 5 and τ (v i v i+1 ) = 2i+2 mod 5 for every i yields an oriented 6-total-coloring satisfying τ (v 0 ) = τ (v 5 ) = 1.
Note that these total-colorings are compatible, in the sense that there cannot be an arc between vertices colored i and j in one path, and between vertices colored j and i in another. Therefore, combining these colorings yields an oriented 6-total-coloring of -→ C n , which concludes.

(e) χ o ( -→ C 7 ) = 7
Figure 3: The unique optimal oriented total-colorings of small directed cycles.

In the case of small directed cycles, we can even go a bit beyond Theorem 3.4, by showing that, up to permuting and renaming colors, such oriented cycles admit a unique oriented total-coloring assigning the least number of colors possible. This actually holds for directed cycles of length at most 6, while, for longer directed cycles, one can check that this is not true. Theorem 3.7. For every n ∈ {3, 4, 5, 6}, there is a unique oriented total-coloring of

-→ C n with χ o ( -→ C n ) colors.
Proof. For each of the directed cycles mentioned in the statement, an oriented total-coloring assigning the stated number of colors is depicted in Figure 3. These colorings are indeed unique:

• For n ∈ {3, 4}, the total digraph T ( -→ C n
) is an absolute oriented clique, which concludes in this case.

• For n = 5, note that the line digraph L( -→ C 5 ) is a directed 5-cycle. Thus, both -→ C 5 and L( -→ C 5 ) are absolute oriented cliques, meaning that both the five vertices and the five arcs of -→ C 5 must receive distinct colors by any oriented 5-total-coloring of -→ C 5 . Furthermore, since every original vertex of T ( -→ C 5 ) is either adjacent or connected by a directed 2-path to all but one vertex, there is a unique way to totally 5-color -→ C 5 .

• For n = 6, observe that χ o ( -→ C 6 ) = 6, and moreover that no three vertices of T ( -→ C 6 ) can get the same color by an oriented total-coloring since, for any three vertices of T ( -→ C 6 ), at least two of them are adjacent or joined by a directed 2-path. Since T ( -→ C 6 ) has exactly 12 vertices, each color must thus be assigned to exactly two vertices in any oriented 6-coloring of T ( -→ C 6 ). Now, assume that some color appears on two elements u, v that are not antipodal in -→ C 6 . Let X (resp. X ) be the set of vertices on some directed path from u to v (resp. from

v to u) in T ( -→ C 6 ) -{u, v}. Note that X, X , {u, v} is a partition of the vertices of T ( -→ C 6 ).
Since u and v are not antipodal but at distance at least 3 in T ( -→ C 6 ), we have |X| = 4 and |X | = 6 (up to swapping u and v). But now some color must appear twice in X , which is not possible since either it ends up on vertices at distance at most 2 in T ( -→ C 6 ) or on one vertex seeing u but seen by v, a contradiction since u and v get the same color. Therefore, each color class is a pair of antipodal elements, which concludes.

Connections between the oriented total chromatic number and other parameters

In this section, we explore how the oriented total chromatic number of an oriented graph relates to others of its chromatic parameters, such as its oriented chromatic number, its oriented chromatic index, or the acyclic chromatic number of its underlying graph.

Connections between the three oriented chromatic parameters

As a starting point, let us recall that, for any given graph G, one can obtain a proper (n + m)total-coloring of G by combining a proper n-coloring and a proper m-edge-coloring of G in the obvious way. In other words, χ (G) χ(G) + χ (G) holds for every graph G. As depicted in Figure 4, the same argument does not hold in the oriented setting: we provide an oriented graph colored so that colors {1, 2, 3} induce an oriented 3-coloring and colors {4, 5, 6} induce an oriented 3-arc-coloring, but the associated 6-total-coloring is not oriented (since colors 3 and 5 appear on two pairs of elements that flow to each other in opposite directions).

Due to such issues, it is not clear that the inequality χ χ + χ still holds in the oriented setting. We leave this as an open question.

Question 4.1. Do we have χ o ( - → G ) χ o ( - → G ) + χ o ( - → G ) for every oriented graph - → G ?
Note that the oriented graph -→ G from Figure 4 does not stand as a counterexample since

χ o ( - → G ) = χ o ( - → G ) = 3 and χ o ( - → G ) = 5.
Another interesting problem is to determine how good the upper bound in Question 4.1 would be (if it holds). In other words, how large can be the difference |χ o + χ o -χ o |. As already shown by Theorem 3.4, the directed 5-cycle has all its oriented chromatic parameters equal to 5, hence the difference can be at least 5. Through a generalisation of this example, we provide a construction

showing that the difference |χ o ( - → G ) + χ o ( - → G ) -χ o ( - → G )|
→ G satisfying χ o ( - → G ) = χ o ( - → G ) = χ o ( - → G ) = 5k, and thus |χ o ( - → G ) + χ o ( - → G ) -χ o ( - → G )| = 5k.
Proof. Let k 1 be fixed, and let -→ G be the oriented graph constructed as follows. Start from the disjoint union of k copies -→ X 1 , . . . , -→ X k of the directed 5-cycle -→ C 5 . Now, for every 1 i < j k, add an arc from every vertex of -→ X i to every vertex of -→ X j . Note that every two vertices of -→ G are either adjacent or joined by a directed 2-path. Similarly, every two arcs ab and cd either are at distance at most 2 in some -→ X i , or they belong to different -→ X i 's in which case bc or da is an arc. From this, we deduce that -→ G is an absolute oriented clique, and thus χ o ( -→ G ) = 5k, and that the arcs of the -→

X i 's induce a relative oriented clique in L( - → G ), and thus χ o ( - → G ) 5k. The fact that χ o ( - → G ) = 5k implies also that χ o ( - → G ) 5k. To see now that we also have χ o ( - → G ) = χ o ( - → G ) 5k
, consider the following 5k-total-coloring of -→ G . For every directed 5-cycle -→ X i , start from any vertex, and go along its elements (vertices and arcs) in order, assigning colors 1 i , 2 i , 3 i , 4 i , 5 i , 1 i , 2 i , 3 i , 4 i , 5 i as traversing them, just as depicted in Figure 3(c). Now, for every arc xy such that x belongs to some -→ X i and y belongs to some -→ X j with i < j, assign to xy the same color as that assigned to x y, where x y is the unique arc in-coming to y in -→ X j . It can be checked that the resulting 5k-total-coloring of

- → G is oriented. Thus, χ o ( - → G ) 5k, and the result follows since χ o ( - → G ) χ o ( - → G ).
It is worth recalling that, for an oriented graph -→ G , we always have

χ o ( - → G ) χ o ( - → G
). Indeed, one can always convert an oriented coloring f into an oriented arc-coloring f by setting f (uv) = f (u) for every arc uv. Thus, a positive answer to Question 4.1 would imply that we always have

χ o ( - → G ) 2 • χ o ( - → G ).
We show that this bound holds through an ad hoc proof.

Theorem 4.3. For every oriented graph

- → G , we have χ o ( - → G ) χ o ( - → G ) 2 • χ o ( - → G ).
Proof. The lower bound being obvious, we focus on proving the upper bound. Set χ o ( -→ G ) = n, and let f be an oriented n-coloring of -→ G assigning colors in {1, . . . , n}. Consider τ , the 2n-total-coloring of -→ G obtained by setting τ (u) = f (u) for all u ∈ V ( -→ G ) and τ (uv) = f (u) + n for all uv ∈ A( -→ G ). We conclude by showing that τ is actually an oriented total-coloring. Observe that by construction, τ never assigns the same color to a vertex and an arc. Therefore, if two elements x, y satisfy τ (x) = τ (y), then either x, y are both arcs, with sources x , y and f (x ) = τ (x ) -n = τ (y ) -n = f (y ), or they are vertices and setting x = x and y = y yields again f (x ) = τ (x) = τ (y) = f (y ). The directed cycles -→ C 4 and -→ C 5 show that the bounds in Theorem 4.3 are tight, since their oriented chromatic numbers are respectively 4 and 5 (see [START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF]), while their oriented total chromatic numbers are respectively 8 and 5 by Theorem 3.4.

We now establish a connection between the oriented total chromatic number of an oriented graph and its oriented chromatic index. It is worth mentioning that the proof technique in the next proof builds upon one developed by Ochem, Pinlou, and Sopena in [START_REF] Ochem | On the oriented chromatic index of oriented graphs[END_REF], which allowed them to express bounds on the oriented chromatic number in terms of oriented chromatic index.

∈ V ( - → G ), let f (u) = {g(uv) : uv ∈ A( - → G )}.
We claim that f is an oriented coloring of -→ G . Indeed, consider any two arcs wx and yz of -→ G . Note that every arc xv must satisfy g(xv) = g(wx). In particular, g(wx) ∈ f (w) but g(wx) ∈ f (x), hence f (w) = f (x). Assume now that f (w) = f (z) and f (x) = f (y). Then g(wx) ∈ f (w) = f (z), and hence there exists a vertex u such that g(zu) = g(wx). Similarly, there exists a vertex v such that g(xv) = g(yz). Now wx flows to xv and yz flows to zu, a contradiction to g being an oriented arc-coloring.

Let us now color vertices of -→ G with f and arcs with g. We claim that the resulting assignment τ is an oriented total-coloring. This would conclude since τ uses at most

k + 2 k colors. Let a, b, c, d ∈ V ( - → G ) ∪ A( - → G )
( - → G ) = k + 2 k for an oriented graph - → G with χ o ( - → G ) = k?

Connections with the acyclic chromatic number

Recall that an acyclic k-coloring of a graph G is a proper k-coloring such that the vertices of G assigned any two distinct colors i, j induce a forest. The acyclic chromatic number χ a (G) of G is the minimum k such that G admits an acyclic k-coloring.

We now establish connections between the oriented total chromatic number of an oriented graph and the acyclic chromatic number of its underlying graph. Our main result reads as follows:

Theorem 4.6. For every oriented graph -→ G with underlying graph G of acyclic chromatic number k, we have

χ o ( - → G ) k • 2 k-1 + 2k(k -1).
Note that if Question 4.1 had a positive answer, then it would imply the theorem, by using two bounds from [START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF], namely:

χ o ( - → G ) k • 2 k-1 and χ o ( - → G ) 2k(k -1) -k/2 for every oriented graph - → G with χ a (G) = k.
In our case, we show that the constructions from [START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF] of a coloring and an arc-coloring satisfying these bounds can be combined into an oriented total-coloring.

Before proving Theorem 4.6, we first need two observations. Recall that even though forests are of unbounded chromatic index in general, all oriented forests are orientedly 3-arc-colorable [START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF]. Observation 4.8 thus means that up to paying one more color, one can "synchronise" an oriented arc-coloring with a bipartition of the underlying graph. Now we are ready to prove Theorem 4.6.

Proof of Theorem 4.6. Let c be an acyclic coloring of G with colors from {1, . . . , k}. For 1 i < j k, we denote by --→ F i,j the oriented forest induced, in -→ G , by c -1 ({i, j}). For all distinct i, j ∈ {1, . . . , k}, take f i,j = (f 1 i,j , f 2 i,j ) and g i,j the oriented 4-coloring and oriented 4-arc-coloring of --→ F i,j obtained through Observations 4.7 and 4.8. Our goal is to obtain an oriented total-coloring of -→ G by combining the f i,j 's and g i,j 's in some fashion. Note that for each arc of -→ G , there exists a unique i < j such that xy ∈ A( --→ F i,j ). In that case we assign color τ (xy) = (g i,j (xy), i, j) to xy. We then color each vertex x such that c(x) = i with

τ (x) = c(x), f 2 1,i (x), f 2 2,i (x), . . . , f 2 (i-1),i (x), f 2 i,(i+1) (x), . . . , f 2 i,k (x) .
Thus f 1 i,j (a) = c(a) = c(d) = f 1 i,j (d) and f 2 i,j (a) = f 2 i,j (d), hence f i,j (a) = f i,j (d)
. Similarly, we get f i,j (b) = f i,j (c), which is not possible since f i,j is an oriented coloring of --→ F i,j .

• If a, b, c, d are all arcs, then we get g i,j (a) = g i,j (d) and g i ,j (b) = g i ,j (c) for some i = j and i = j . Since a flows to b and c to d, then we must have i = i and j = j . But this is not possible, since g i,j is an oriented arc-coloring of --→ F i,j .

i,j that f i,j (a) = g i,j (b) = g i,j (c) = f i,j (c ).
But this is a contradiction since f i,j is an oriented coloring of --→ F i,j .

Again, we leave open the question of whether the bound in Theorem 4.6 is tight in general.

Question 4.9. Can we have

χ o ( - → G ) = k • 2 k-1 + 2k(k -1)
for an oriented graph -→ G with underlying graph G of acyclic chromatic number k?

Complexity dichotomy

We here consider the decision problem OTC k , which asks whether a given oriented graph -→ G admits an oriented k-total-coloring. Note that OTC k is clearly in NP for every k. Our main result in this section is a full dichotomy for the complexity of this problem, namely: Theorem 5.1. OTC k is NP-complete for all k 6 and is polynomial-time solvable otherwise.

As reported in [START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF], it is known that the problem of deciding whether a given oriented graph has oriented chromatic number or oriented chromatic index k is polynomial-time solvable for every k 3 and NP-complete otherwise, i.e., if k 4.

We start by proving the polynomial cases of Theorem 5.1, which actually can be established from results we have proved earlier.

Theorem 5.2. OTC k is polynomial-time solvable for every k 5. Moreover, in each case, an oriented k-total-coloring can be found in polynomial time when it exists.

Proof. Let -→ G be an oriented graph. Remind that, through Theorem 3.1, we have given a characterization of oriented graphs with oriented total chromatic number in {1, 2, 3, 4}. Particularly, remind that the oriented total chromatic number of an oriented graph can never be equal to 2 or 4. Now,

to check if χ o ( - → G ) = 1, it suffices to check whether - → G has no arcs, while, to check if χ o ( - → G ) = 3, it suffices to check whether - →
G has arcs and all vertices are sources and sinks. These properties can clearly be checked in polynomial time; actually, note that, in these cases, even constructing an oriented 1-total-coloring or an oriented 3-total-coloring can be done in polynomial time (using the constructive proof of Theorem 3.1). Now, by Theorem 3.

a -→ T 5 -coloring of T ( - → G ), which is again equivalent to finding a homomorphism f : - → G → -→ T 5
where each arc xy is mapped to an arc i(i + 2) in -→ T 5 . Such a coloring f can be obtained as follows. Choose an arbitrary vertex v and a spanning tree T of G rooted at v. Now set f (v) = 1, and color the remaining vertices as follows: consider an edge xy of T such that y is colored but x is not, and color x with f (y) -2 mod 5 if xy ∈ A( -→ G ) and f (y) + 2 mod 5 if yx ∈ A( -→ G ). Now, let xy be an arc in -→ G but not in T and let σ be the signature of the closed walk of G formed by taking the edge xy and then the path in T between y and x. By summing f (a) -f (b) for each edge ab in this walk, we end up with 0 = f (y) -f (x) + 2σ -2 hence either f (y) = f (x) + 2 mod 5 or σ is not a multiple of 5, and we can conclude that χ o ( -→ G ) > 5. Therefore, in polynomial time, either we find an obstruction and can answer negatively, or we correctly construct f . We now focus on proving the NP-hardness of OTC k for every k 6. For that, we need to consider the decision problem OTC * k , which is the restriction of OTC k to oriented graphs -→ G that have neither sources nor sinks. Indeed, it turns out that we have the following connections between the OTC k and OTC * k problems:

Lemma 5.3. If OTC * k is NP-hard for some k, then OTC k+1 , OTC k+2 and OTC * k+3 are NP-hard.
Proof. Assume OTC * k is NP-hard for some k. The result follows from the following three dedicated polynomial-time reductions, performed from an oriented graph -→ G being an instance of OTC * k .

• Regarding OTC k+1 , consider the following construction from -→ G . Let -→ H be the oriented graph obtained from -→ G by adding a new vertex s dominating all other vertices (i.e., sx is an arc for every x ∈ V ( -→ G )). We claim that -→ G admits an oriented k-total-coloring if and only if -→ H admits an oriented (k + 1)-total-coloring.

Assume first that

-→ H admits an oriented (k + 1)-total-coloring τ . Because s dominates all other vertices, note that the color τ (s) must be assigned to s only. This means that the restriction of τ to -→ H -s, thus to -→ G , must be an oriented k-total-coloring.

Assume now that -→ G admits an oriented k-total-coloring τ . We extend τ to an oriented (k + 1)-total-coloring τ of -→ H , by assigning color k + 1 to s, and for each arc sx, by defining Due to Lemma 5.3, Theorem 5.1 boils down to prove that OTC * 6 is NP-hard, which is the goal of the rest of this section. We first need to introduce some gadgets and to point out some of their properties. The first two gadgets, the target gadget ----→ G target and the target -→ T , are depicted in Figure 5. Throughout what follows, we deal with their vertices and arcs through the terminology given in the figure. Proof. Assume ----→ G target admits an oriented 6-total-coloring τ , and that τ is an -→ H -total-coloring for some oriented graph -→ H on 6 vertices (where V ( -→ H ) = {0, 1, 2, 3, 4, 5}). By Theorem 3.7, recall that a directed triangle, up to renaming the colors, is uniquely orientedly 6-total-colorable. Consequently, we may assume that τ (a) = 0, τ (ab) = 1, τ (b) = 2, τ (bc) = 3, τ (c) = 4, and τ (ca) = 5. This determines the direction of all the arcs of -→ H (which are as in -→ T , in Figure 5 Based on the in-degrees and out-degrees in -→ T , we say that colors 0, 1, 5 are weak while colors 2, 3, 4 are strong. Furthermore, we say that a pair (c, c

τ (sx) = τ (yx) where y is a vertex of - → G such that yx ∈ A( - → G ) (such
) ∈ V ( - → T ) × V ( - → T ) of colors is good if c is weak, c is
strong, and c = c + 3 mod 6. Note that the only good pairs are thus (0, 3), [START_REF] Borodin | On acyclic colorings of planar graphs[END_REF][START_REF] Borodin | On universal graphs for planar oriented graphs of a given girth[END_REF] and (5, 2) (here and further, operations over vertices of -→ T are understood modulo 6). -→ T -total-colorings τ of -→ V , realizing any given good pair as (τ (w), τ (s)).

• If τ (s) = 4, then, because ws is an arc, we have τ (w) ∈ {1, 2}. By Lemma 5.5 applied to the directed 4-path linking w to d, we get that τ (w) = 1.

Thus, (τ (w), τ (s)) must be a good pair, as claimed. For the last part, we provide in Figure 7 some colorings satisfying the requested properties.

We finish off by pointing out useful properties of -→ T -total-colorings in oriented graphs containing directed paths of certain length. Proof. Towards a contradiction, assume τ (s) is weak, τ (t) is strong, and τ (s) = τ (t) + 3. Let us denote by x the middle vertex of -→ P and note that x is at distance precisely 4 from both s and t in P . Applying Lemma 5.5 twice (from s to x and from x to t) thus gives that

τ (x) ∈ {τ (s) + 2, τ (s) + 3, τ (s) + 4} ∩ {τ (t) -2, τ (t) -3, τ (t) -4}.
Now, since τ (s) = τ (t) + 3, this intersection is empty, implying that there is no valid color for x by τ , a contradiction. 2. τ (tx) = τ (t) + 1 for every arc tx;

3. τ (s) is weak, τ (t) is strong, and τ (s) = τ (t) + 3.

Then the oriented graph obtained from -→ H by adding a directed 8-path from s to t admits a -→ T -total-coloring extending τ .

(c) (c, c ) = (0, 2) 0 2 4 0 2 4 0 2 4 5 1 3 5 1 3 5 1 3 5 (d) (c, c ) = (0, 4) 1 4 0 3 5 2 4 0 2 0 3 5 2 4 0 3 5 1 3 (e) (c, c ) = (1, 2) 1 4 0 3 5 2 4 0 3 0 3 5 2 4 0 3 5 2 4 (f) (c, c ) = (1, 4) Figure 8:
-→ T -total-colorings τ of -→ P , showing that Lemma 5.8 is true.

Proof. By hypothesis, it is sufficient to consider the directed path -→ P = x 1 . . . x 11 of length 10, and to show that, for every pair (c, c ) that is not good, there exist -→ T -total-colorings τ of -→ P such that τ (x 2 ) = c, τ (x 10 ) = c , τ (x 1 x 2 ) = c -1 and τ (x 10 x 11 ) = c + 1. We provide, in Figure 8, such -→ T -total-colorings for each of the six pairs of {0, 1, 5} × {2, 3, 4} to consider as (c, c ).

We now conclude this section by showing the NP-hardness of OTC * 6 , which implies Theorem 5.1. To this end, we reduce the 3-Coloring problem, which is well known to be NP-hard.

The construction goes as follows. Let G be an instance of 3-Coloring. First, for every vertex v of G, we add, in -→ H , a copy -→ V v of the vertex gadget -→ V , for which we denote by w v and s v its vertices w and s. We then consider every edge uv of G, and join, in -→ H , the vertices w u and s v (resp. w v and s u ) via a new directed 8-path (i.e., its internal vertices being new vertices) from w u to s v (resp. from w v to s u ). Observe that -→ H has neither sources nor sinks, due to the structure of -→ V , and that this oriented graph can be computed in polynomial time.

It remains to show that G is properly 3-colorable if and only if -→ H has an oriented 6-totalcoloring:

• Assume -→ H admits an oriented 6-total-coloring τ . Since -→ H contains copies of the vertex gadget -→ V , by Lemma 5.6, actually τ must be a -→ T -total-coloring. Also, for every v ∈ V (G), the pair (τ (w v ), τ (s v )) must be good. Recall that there are only three good pairs, namely (0, 3), [START_REF] Borodin | On acyclic colorings of planar graphs[END_REF][START_REF] Borodin | On universal graphs for planar oriented graphs of a given girth[END_REF] and (5, 2). Furthermore, for every uv ∈ E(G), the vertices w u and s v of -→ H are joined by a directed 8-path from w u to s v , and by Lemma 5.7 it must be that τ (w u ) is weak, τ (s v ) is strong, the pair (τ (w u ), τ (s v )) is not good, and thus τ (w u ) = τ (s v ) + 3. This implies that the good pairs (τ (w u ), τ (s u )) and (τ (w v ), τ (s v )) are not the same. From this, we deduce that considering every vertex v ∈ V (G) and assigning color τ (s v ) to v, we obtain a proper 3-coloring of G.

• Conversely, assume G admits a proper 3-coloring assigning colors 0, 1, 5. Consider the

- → T - total-coloring τ of - →
H obtained as follows. For every vertex v ∈ V (G), we set τ (w v ) = τ (v) and τ (s v ) = τ (v) + 3. By Lemma 5.6, the resulting partial total-coloring τ extends in an oriented way to all the -→ V v 's. From the fact that τ is proper and that the resulting τ can be assumed to satisfy all properties in Lemma 5.6, the resulting τ actually verifies all conditions in Lemma 5.8, which extends in an oriented way also to the remaining elements of -→ H . As a result, we eventually obtain a

- → T -total-coloring of - → H .
This concludes the proof of Theorem 5.1.

Oriented planar graphs

To make the results in this section more legible, we extend the oriented total chromatic number to graphs, by defining χ o (G) for a graph G as the maximum of χ o ( -→ G ) over all orientations -→ G of G. We also extend it to families of graphs, by defining χ o (F) for a family F of graphs as the maximum of χ o (G) over all members G of F. Similarly, we extend all chromatic notions considered earlier to graphs and families of graphs.

A common class of graphs to consider when dealing with a new coloring problem is that of planar graphs. For g 3, we define P g as the family of planar graphs with girth at least g, i.e., in which shortest cycles have length at least g. Note that P 3 is the class of all planar graphs.

Note that results we have proved earlier provide first upper bounds on χ o (P 3 ). Notably, we get χ o (P 3 ) 160 from Theorem 4.3 and χ o (P 3 ) 38 + 2 38 from Theorem 4.4, since oriented planar graphs have oriented chromatic number at most 80 and oriented chromatic index at most 38 (see [START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF]). Using that planar graphs have acyclic chromatic number at most 5 (see [START_REF] Borodin | On acyclic colorings of planar graphs[END_REF]), Theorem 4.6 also provides the following. Theorem 6.1. χ o (P 3 ) 120.

In the rest of this section, we deal with restricted oriented planar graphs. Namely, we deal with oriented planar graphs with large girth, and oriented outerplanar graphs.

Oriented planar graphs with large girth

A common trend when coloring planar graphs is that they require less and less colors when their girth increases, with some stabilization for large enough girths, similarly to what happens with standard coloring: χ(P g ) = 3 for g 4 by Grötzsch's Theorem. In the oriented setting, it is known that χ o (P g ) = 5 for every g 12 and χ o (P g ) 4 for every g 46 (see [START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF]). For oriented total-coloring, this still holds, as shown by the following. Theorem 6.2. For every g 26, we have χ o (P g ) = 7.

We start by proving the upper bound in Theorem 6.2. Lemma 6.3. For every g 26, we have χ o (P g ) 7. Proof. This is proved by showing that for every oriented planar graph -→ G such that G has girth g 26, its total digraph T ( -→ G ) admits a homomorphism to -→ T 7 , the oriented graph depicted in Figure 9. Towards a contradiction, assume this is wrong, and let -→ M be a minimal counterexample (in terms of order). That is, M ∈ P g and the total digraph of -→ M does not admit a homomorphism to -→ T 7 . By minimality, M is connected. Also, we know that M , due to its girth, contains either a vertex v of degree 1, or a 6-path x 0 • • • x 6 whose internal vertices x 1 , . . . , x 5 have degree 2 (see [START_REF] Borodin | On the maximum average degree and the oriented chromatic number of a graph[END_REF]). We exhibit in each case a contradiction with the minimality of -→ M .

• Assume M contains a degree-1 vertex v with unique neighbor u. Then, by minimality of -→ M , there must be a homomorphism f :

T ( -→ M -v) → -→ T 7 .
Since -→ T 7 is vertex-transitive, without loss of generality we may assume that f (u) = 0.

We extend f to T ( -→ M ) by setting f (v) = 5 and f (e vu ) = 6 if v is an in-neighbor of u, and f (v) = 2 and f (e uv ) = 1 otherwise, a contradiction.

• Assume M contains a 6-path x 0 • • • x 6 whose internal vertices have degree 2. By minimality of -→ M , the oriented graph -→ M -{x 1 , . . . , x 8 } admits a -→ T 7 -total-coloring f . Due to the vertextransitivity and the arc-reversal symmetry of -→ T 7 , without loss of generality we may assume that f (x 0 ) = 0 and x 1 is an out-neighbor of x 0 . Moreover, assume that f

(x 6 ) = i ∈ V ( -→ T 7 ).
Observe now that it is possible to extend f correctly to x 1 and x 0 x 1 by setting f (x 0 x 1 ) = 1 and f (x 1 ) ∈ {2, 3}. Indeed, every arc going to x 0 is colored with 5 or 6 (since the in-neighbor of x 0 incident to that arc is colored 4 or 5). Similarly, we can color the arc between x 5 and x 6 with i ± 1 mod 7 (depending on its orientation). Now, one can show by induction that for every j, there are at least j + 1 colors that are possible for x j , meaning that if we set f (x j ) to be one of them, then we can extend f to the oriented path from x 0 to x j . To obtain a homomorphism of T ( -→ M ) to -→ T 7 , note that either i -2 or i -3, and either i + 2 or i + 3 have to be among the six possible colors for x 5 . We may thus color x 5 regardless of the orientation of the arc x 5 x 6 , a contradiction.

We now focus on proving the lower bound in Theorem 6.2. Note that Theorems 3.3 and 3.4 already provide that χ o (P g ) 6 holds for every g 26. Towards a contradiction, let us assume that χ o (P g ) = 6. Since P g is closed under taking disjoint unions of graphs, there must exist a tournament -→ T 6 such that every orientation of a graph in P g admits a -→ T 6 -total-coloring. In what follows, we investigate what -→ T 6 should look like.

Lemma 6.4.

-→ T 6 contains exactly three vertices with out-degree 3 and in-degree 2, while the other three vertices have in-degree 3 and out-degree 2.

Proof. It suffices to show that every vertex of -→ T 6 has out-degree and in-degree at least 2. Recall that, whatever g 26 is, there exists an oriented cycle

( - → C * ) → -→ T 6 . Since χ o ( - → C ) = 6
, each color must appear on some x in the unique cycle of C * . But then the vertices x + and e xx + (resp. x -and e x -x ) must be mapped, in -→ T 6 , to distinct out-neighbors (resp. in-neighbors) of τ (x), which concludes.

We now prove a key structural property of -→ T 6 .

Lemma 6.5.

-→ T 6 does not contain a transitive oriented 3-cycle with source x and sink y such that the out-degree of x and the in-degree of y are both 2 in -→ T 6 .

Proof. Assume this is wrong, i.e., suppose -→ T 6 contains a transitive oriented 3-cycle with source x and sink y such that the out-degree of x and the in-degree of y are both 2 in -→ T 6 .

Consider an orientation

- → A of a (2g + 1)-cycle A = u 0 u 1 v 1 u 2 v 2 .
. . u g v g u 0 where each v i is a sink and u 0 is a source. Let τ : T ( -→ A ) → -→ T 6 be a homomorphism. If τ (u 1 ) = x, then we must have τ (v i ) = y and τ (u i ) = x for every i ∈ {1, . . . , g}. This implies τ (u 0 ) = τ (u 1 ) while u 0 and u 1 are adjacent. -→ A u . Since τ (u 1 ) = x, then we must have τ (v i ) = y and τ (u i ) = x for every i ∈ {1, . . . , g}. This implies τ (u 0 ) = τ (u 1 ) while u 0 and u 1 are adjacent, a contradiction.

We are now ready to show that there is only one candidate tournament as -→ T 6 . Lemma 6.6.

v 1 v 2 v 3 u 1 u 2 u 3
-→ T 6 is the tournament depicted in Figure 10.

Proof. By Lemma 6.4, we know that -→ T 6 contains exactly three vertices u 1 , u 2 , u 3 having out-degree 3 and in-degree 2. Also, the other three vertices v 1 , v 2 , v 3 of -→ T 6 have in-degree 3 and out-degree 2. For every i ∈ {1, 2, 3}, the two in-neighbors of u i cannot both belong to {v 1 , v 2 , v 3 } due to Lemma 6.5, and, thus, {u 1 , u 2 , u 3 } must induce a directed 3-cycle, say u 1 u 2 u 3 u 1 by symmetry. Similarly {v 1 , v 2 , v 3 } must induce a directed 3-cycle, say v 1 v 2 v 3 v 1 . Now, note that the u i 's (resp. v i 's), due to their out-degrees and in-degrees, must have exactly one in-neighbor (resp. out-neighbor) among the v i 's (resp. u i 's). Without loss of generality, we have the arc v i u i for every i ∈ {1, 2, 3} and all the other arcs are directed from {u 1 , u 2 , u 3 } to {v 1 , v 2 , v 3 }, which concludes.

We end this section by exhibiting an oriented graph -→ G without -→ T 6 -total-coloring and such that G ∈ P g . Consider the directed (3g + 1)-cycle ---→ C 3g+1 = x 0 • • • x 3g x 0 . Note that C 3g+1 is a planar graph with girth at least g. Since χ o (P g ) = 6, there must exist τ : T ( ---→ C 3g+1 ) → -→ T 6 . Observe that for each arc xy, if τ (x) = u i then τ (y) = u i+1 and if τ (x) = v i then τ (y) = v i+1 (where indices are taken modulo 3). In particular, that means we have τ (x 0 ) = τ (x 3g ), which is impossible since these vertices are adjacent. This concludes the proof of Theorem 6.2.

Oriented outerplanar graphs

We now turn our attention to the oriented total chromatic number of outerplanar graphs. Denoting by O the family of all outerplanar graphs, our main result in this section reads as follows: Theorem 6.7. 10 χ o (O) 13.

For comparison, let us mention, see e.g. [START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF], that χ o (O) = χ o (O) = 7. As in the previous section, we split the proof of Theorem 6.7 into smaller proofs. We first prove the upper bound. Proof. By [START_REF] Sopena | The chromatic number of oriented graphs[END_REF], every oriented outerplanar graph admits a homomorphism to the Paley tournament --→ P al 7 (depicted in Figure 11) on 7 vertices. The result now follows from Proposition 2.1 since --→ P al 7 admits an oriented 13-total-coloring (see again Figure 11).

We now focus on proving the lower bound of Theorem 6.7. Lemma 6.9. The oriented outerplanar graph -→ O depicted in Figure 12 does not admit an oriented 9-total-coloring. Proof. Assume this is wrong, that is let τ : V ( -→ O ) → {1, . . . , 9} be an oriented 9-total-coloring of -→ O . By Lemma 2.2, recall that if two vertices of T ( -→ O ) are either adjacent or connected by a directed 2-path, then their corresponding vertices or arcs in -→ O must be assigned distinct colors by τ . This implies that x 1 u, ux 2 , x 2 v, vx 3 , x 3 w, wx 1 , u, v, w must get colored with 1 to 9 in this order (up to renaming colors).

y 1 x 1 z 1 z 3 w u y 2 x 3 v x 2
From this, one can easily check that the only available colors for x 1 , x 2 , x 3 , uv, vw, wu are the ones listed in the following table :   x 1

x 2 x 3 uv vw wu τ 3, 4 5, 6 1, 2 2, 3 4, 5 6, 1 Moreover, either they are all colored with the first element of their list, or they are all colored with the second. In both cases, observe that τ (y 1 x 1 ) cannot lie in {3, 4}. Therefore τ (y 1 x 1 ) ∈ {6, 8}. Similarly, we get the following constraints: Now, if τ (y 1 x 1 ) = 6, then τ (wy 1 ) = 7, hence τ (x 3 z 3 ) = 5, and finally τ (z 3 w) = 8. Therefore, 8 ∈ {τ (y 1 x 1 ), τ (z 3 w)}. But, by symmetry, we also get that 8 ∈ {τ (x 1 z 1 ), τ (uy 2 )}, a contradiction since y 1 x 1 , z 3 w, x 1 z 1 and z 3 w form a relative oriented clique. Thus, -→ O admits no oriented 9-totalcoloring.

x 3 z 3 z 3 w wy 1 y 1 x 1 x 1 z 1 z 1 u uy 2 y 2 x 2 τ 5, 7 5
Note that there is some gap between the two bounds in Theorem 6.7; we thus leave the following question open for now. Question 6.10. What is the exact value of χ o ( -→ O )?

Conclusions

Our main goal in this work was to introduce a notion of total-coloring of oriented graphs that would stand as a generalization of proper total-colorings, fitting in a natural way into the area comprising oriented colorings and oriented arc-colorings. From this point of view, the way the three coloring notions relate, as described in Section 2, is indeed quite reminiscent of the connections between the corresponding three notions in undirected graphs.

Following the previous work on the oriented chromatic number and index yields a wealth of directions for studying oriented total-colorings. In this work, we chose to focus on presenting several kinds of results, about particular families of oriented graphs, connections with other graph parameters, and algorithmic aspects. In this concluding section, we would like to summarize the open questions disseminated throughout this work and present possible directions for further work on the topic.

• Regarding our results in Section 4, certainly the most interesting question is Question 4.1.

Having

χ o ( - → G ) χ o ( - → G ) + χ o ( - → G )
for every oriented graph -→ G would definitely seem very natural, as it would be reminiscent of a similar relationship in the undirected setting, but we failed proving it because of situations such as the one depicted in Figure 4. As mentioned earlier, recall that this inequality, if true, would imply a certain number of things, such as a direct proof of Theorem 4. One additional question could be whether the construction we came up with is a very peculiar one, or whether there exist other constructions that are as worse regarding the difference of these parameters.

Finally, regarding Section 4, recall that we still miss a proof that all bounds are tight in Theorems 4.4 and 4.6, recall Questions 4.5 and 4.9.

• Regarding our results in Section 5, one could wonder about restrictions of Theorem 5.1 in particular classes of oriented graphs. Interesting candidates could include classes of oriented graphs for which determining the oriented chromatic number or oriented chromatic index is hard, such as oriented graphs being bipartite, of bounded degree, acyclic, planar, etc. [START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF].

• Regarding our results in Section 6, improving the upper bound in Theorem 6.1 would definitely be an appealing direction. We did not discuss about lower bounds on χ o (P 3 ), but, due to the fact that χ o (P 3 ) 18 (as proved by Marschall [START_REF] Marshall | On oriented graphs with certain extension properties[END_REF]), we have χ o (P 3 ) 18 as well. Improving any of these two bounds on χ o (P 3 ) would thus be interesting.

In Theorem 6.2, we have determined χ o (P g ) when g 26. A natural question is about oriented graphs with smaller girth, i.e., for any g ∈ {3, . . . , 25}. Again, lower bounds can be established from similar bounds known for the oriented chromatic number, or some of our results such as Theorem 3.4.

Lastly, it would be interesting to refine Theorem 6.7, the two bounds being not that distant from each other. Recall that χ o (O) = χ o (O) = 7, so the class of oriented outerplanar graphs is well understood for the oriented chromatic number and oriented chromatic index.

• In the case of graphs, a common way for bounds on the chromatic number, chromatic index, and total chromatic number to be expressed is by a function of the maximum degree. In particular, for a graph G with maximum degree ∆, we always have χ(G) ∆ + 1 by Brooks' Theorem, χ (G) ∈ {∆, ∆ + 1} by Vizing's Theorem, and it is conjectured, through the Total Coloring Conjecture of Behzad and Vizing, that we always have χ (G) ∆ + 2.

In the case of oriented graphs -→ G , one can similarly wonder abound upper bounds on χ o ( -→ G ) that are functions of some maximum degrees (maximum degree of G, maximum out-degree and in-degree in -→ G , or combinations of these parameters). For instance, setting ∆ = ∆(G), it is known that we always have χ o ( -→ G ) 2∆ 2 • 2 ∆ (see [START_REF] Kostochka | Acyclic and oriented chromatic numbers of graphs[END_REF]), from which we deduce that we always have χ o ( -→ G ) 4∆ 2 • 2 ∆ by Theorem 4.3. One legitimate direction for further research on the topic could be to improve this last upper bound on the oriented total chromatic number.

• Still about the maximum degree ∆ of the underlying graph, one could also wonder about situations where ∆ is small. Let us denote by D ∆ the class of graphs with maximum degree ∆. Through Theorems 3.3 and 3.4, note that we have fully determined the oriented total chromatic number when ∆ = 2, as we proved that χ o (D 2 ) = 8. For comparison, recall that χ o (D 2 ) = χ o (D 2 ) = 5.

In that line, the next natural step to make would be to consider the class D 3 of subcubic graphs. We recall that, for now, it is known that χ o (D 3 ) ∈ {7, 8} and χ o (D 3 ) ∈ {6, 7} (see [START_REF] Duffy | Colourings of oriented connected cubic graphs[END_REF][START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF]). From our results in this work, from Theorem 3.4 we get that χ o (D 3 ) 8, while the best upper bound our results provide, through Theorem 4.3, gives χ o (D 3 ) 16. Thus, quite some efforts remain to be made towards determining χ o (D 3 ).

• Through Theorem 6.2, we have considered oriented graphs with a very sparse structure. In that line, it would be interesting to study the oriented total chromatic number of sparse oriented graphs, which is a line of research that has already been quite investigated regarding the oriented chromatic number and the oriented chromatic index (see [START_REF] Sopena | Homomorphisms and colourings of oriented graphs: An updated survey[END_REF] for pointers). Particularly, one could consider orientations of graphs with bounded maximum average degree, and investigate how the discharging method, which is one of the main tools in this context, can be set to use.

  are such that a flows to b and c flows to d, then τ (a) = τ (d) implies τ (b) = τ (c).

Figure 1 :

 1 Figure 1: Constructing the subdivision and total versions of a graph or oriented graph.

Theorem 3 . 2 .

 32 An oriented graph -→ G verifies χ o ( -→ G ) 5 if and only if one of the following holds:

Figure 2

 2 Figure 2: The tournament -→ T 5 .

Figure 4 :

 4 Figure 4: Combining an oriented coloring (a) and an oriented arc-coloring (b) assigning distinct colors in an oriented graph does not have to result in an oriented total-coloring (c).

••

  Moreover, if x flows to y then x flows to y . Let a, b, c, d be elements of -→ G such that a flows to b and c flows to d. Assume that τ (a) = τ (b). Then f (a ) = f (b ) and a flows to b , a contradiction since f is an oriented coloring. Assume that τ (a) = τ (d) and τ (b) = τ (c). Again, we get vertices a , b , c , d such that f (a ) = f (d ) and f (b ) = f (c ). One can also observe that either a = b (if a is a vertex and b is an arc) or a flows to b (otherwise). Similarly, either c = d or c flows to d . In each case, we get again a contradiction.

Theorem 4 . 4 .

 44 Every oriented graph -→ G of oriented chromatic index k satisfies k χ o ( -→ G ) k+2 k .Proof. The lower bound being obvious, let us focus on proving the upper bound. Let g : A( -→ G ) → S be an oriented k-arc-coloring of -→ G where |S| = k. We color each vertex with the set of the colors of the arcs leaving it. More precisely, for each u

Question 4 . 5 .

 45 be such that a flows to b and c flows to d. Since f and g are oriented colorings and τ assigns colors from disjoint sets to vertices and arcs, we already have that τ (a) = τ (b). Assume now that τ (a) = τ (d) and τ (b) = τ (c). In this case, a and d (resp. b and c) must be either both vertices or both arcs. If all of a, b, c, d are vertices (resp. arcs), then we reach a contradiction as f (resp. g) is an oriented (resp. arc) coloring. By symmetry, assume that a and d are both vertices and b and c are both arcs. In particular, b is out-going from a and c is in-coming to d. Since g(b) ∈ f (a) = τ (a) = τ (d) = f (d), there exists an arc de with τ (de) = g(b) = τ (b). But then c flows to de and τ (c) = τ (b) = τ (de), which is impossible. The lower bound in Theorem 4.4 is tight, as shown by the directed 5-cycle: χ o ( -→ C 5 ) = χ ( -→ C 5 ) = 5. Regarding the upper bound, we leave open the question of whether it is tight. Can we have χ o

Observation 4 . 7 .

 47 Let -→ F be an oriented forest. Then we can extend any proper 2-coloring c of F into an oriented 4-coloring f : V ( -→ F ) → {1, 2}×{0, 1} such that projecting f on the first component yields c. Proof. We can simply color -→ F recursively: if y is a leaf in F with neighbor x colored f (x) = (c(x), α), we set f (y) = (c(y), β) where β ∈ {0, 1} satisfies α = β if and only if c(x) < c(y).

  Through coloring again arcs by the color of their source vertex, we obtain the following arc version of previous Observation 4.7. Observation 4.8. Let -→ F be an oriented forest. Then we can extend any proper 2-coloring c of F into an oriented 4-arc-coloring g : A( -→ F ) → {1, 2} × {0, 1} such that for every arc xy, projecting g(xy) on the first component yields c(x).

  Note that there are k • 2 k-1 possible colors for vertices and 4 × k 2 possible colors for arcs. It remains to prove that τ is indeed an oriented total-coloring of -→ G . Let a, b, c, d be elements of -→ G such that a flows to b and c flows to d. If τ (a) = τ (b), then a, b are both vertices or both arcs since τ assigns disjoint colors to vertices and arcs. The former cannot happen for otherwise c(a) = c(b) but a and b are adjacent in G. In the latter case, we get g i,j (a) = g j,k (b) where i, j, k are the colors under c of the ends of a and b. By projecting on the first component, we get i = j, which is impossible since the ends of a are colored with i and j under c. Therefore τ (a) = τ (b). Similarly, assume that τ (a) = τ (d) and τ (b) = τ (c). Then, a and d (resp. b and c) must be either both vertices or both arcs. We consider several cases: • If a, b, c, d are all vertices, then we get c(a) = c(d) = i and c(b) = c(c) = j for some i = j.

•

  Otherwise, assume by symmetry that a and d are vertices and b and c are arcs. In particular, a is the source vertex of b and d is the target vertex of c. From τ (a) = τ (d) we get c(a) = c(d), and from τ (b) = τ (c) we get that the ends of b and c are colored with two colors i, j (note that c(a) is one of them), and moreover, g i,j (b) = g i,j (c). Projecting τ (a) = τ (d) on the correct component, we get f i,j (a) = f i,j (d). Moreover, denoting by c the source of c (so that c = c d and c flows to d), we get by definition of g

Figure 5 :Lemma 5 . 4 .

 554 Figure 5: The target -→ T and the target gadget ----→ Gtarget, with its only possible oriented 6-total-colorings.

  (a)), except for the edges 03, 14 and 25 that are yet not oriented. Since ad is an arc and τ (a) = 0, we must have τ (d) ∈ {1, 2, 3}. Actually, we cannot have τ (d) = 2 because de and eb are arcs and τ (b) = 2. Moreover, we cannot have τ (d) = 1 as otherwise there would not be any possible color for ad. Hence τ (d) = 3 and -→ H contains the arc 03. This implies that τ (e) ∈ {4, 5}, and τ (e) = 4 since eb is an arc with τ (b) = 2. Therefore τ (e) = 5 and -→ H contains the arc 52. Finally, because of the arc f c and f d, we must have τ (f ) ∈ {1, 2}. But if τ (f ) = 2, then f d cannot be colored, hence τ (f ) = 1, and due to the arc f c, can then easily be checked that there is no more choice left for the colors of the arcs except for ad, as shown in Figure 5(b).

  (τ (w), τ (s)) =[START_REF] Borodin | On the maximum average degree and the oriented chromatic number of a graph[END_REF][START_REF] Borodin | On deeply critical oriented graphs[END_REF]

Figure 7 :

 7 Figure 7:-→ T -total-colorings τ of -→ V , realizing any given good pair as (τ (w), τ (s)).

Lemma 5 . 7 .

 57 Let -→ P = s • • • t be the directed 8-path, and τ be a -→ T -total-coloring of -→ P .Then the pair (τ (s), τ (t)) cannot be good.

Lemma 5 . 8 .

 58 Let -→ H be an oriented graph, and τ be a -→ T -total-coloring of -→ H . Assume s and t are two vertices of -→ H , such that: 1. τ (xs) = τ (s) -1 for every arc xs;

Figure 9 :

 9 Figure 9: The tournament -→ T 7 .

  the oriented graph obtained by attaching a new pending out-neighbor x + and a new pending in-neighbor x -at every vertex x of -→ C . By our assumption, there exists a homomorphism τ : T

Figure 10 :

 10 Figure 10: The tournament -→ T 6 .

Lemma 6 . 8 .

 68 χ o (O) 13.

Figure 11 :

 11 Figure 11: The Paley tournament --→ P al 7 on 7 vertices together with an oriented 13-total-coloring.

Figure 12 :

 12 Figure 12: An oriented outerplanar graph with oriented total chromatic number 10.

3 .

 3 In connection with Question 4.1, we proved through Theorem 4.2 that the difference ofχ o ( -→ G ) + χ o ( -→ G ) and χ o ( -→ G) can be arbitrarily large for an oriented graph -→ G .

  is obtained when replacing each of its arcs uv by a directed 2-path ue uv v, where e uv is a new vertex. Now, the total digraph of

	digraph S( -→ G ) -→ G , denoted by T ( -→ G ), is obtained from S( -→ G ) by adding an arc from any vertex u to any vertex v if, in S( -→ G ), there is a directed path of length at most 2 from u to v. In S( -→ G ) and T ( -→ G ), the e uv 's are called new vertices while the other vertices are called original vertices. Note that the subgraph of T ( -→ G ) induced by the original vertices is -→ G . Moreover, the subgraph of T ( -→ G ) induced by the new vertices is the line digraph L( -→ G ) of -→ G (see
	e.g. [12]). Remark now that an oriented arc-coloring of for some oriented graph -→ H (which yields an -→ H -arc-coloring of -→ G can be seen as a homomorphism L( → -G ) → -→ G ), while an oriented total-coloring -→ H of -→ G can be seen as a homomorphism T ( -→ G ) → -→ H for some oriented graph -→ H (which yields an -→ H -total-coloring of -→ G ). Now, as for the oriented chromatic number, the oriented chromatic index χ o ( -→ G ) of -→ G is the smallest n such that -→ G admits an -→ H -arc-coloring for some oriented graph -→ H
	of order n, while the oriented total chromatic number χ o
	For an oriented graph	-→ G , its subdivision

  2, R being a relative oriented clique does not mean that χ o (

	-→ G [R]) = |R|, since vertices of R may be forced to receive distinct colors because of vertices and arcs of -→ G not in -→ G [R]. This
	justifies the introduction of the distinct notion of absolute oriented cliques, which are subsets S of vertices inducing an oriented graph with oriented chromatic number |S|. We denote by ω a ( -→ G ) and ω r ( -→ G ) the size of the largest absolute oriented cliques and relative oriented cliques of -→ G ,
	respectively. Note that we get from the definitions that ω a

  directed 3-paths, or the signatures of the closed walks of G are multiples of 5. Note that determining the length of the longest directed paths of an oriented graph can clearly be done in polynomial time. If the longest directed paths of

	2, we have χ o ( → -G ) 5 if and only if	-→ G is consistent, meaning that either
	it has no -→ G have length 2, then an oriented 5-total-coloring can be obtained in polynomial time by coloring -→ G as described in the proof of Theorem 3.2. Otherwise, checking whether -→ G admits oriented 5-total-colorings is equivalent to
	finding

  case, i.e., add s and t as above, and also add the arc ts.

			vertex exists since	-→ G
	has no source).
	• For OTC k+2 , consider nating all vertices of -→ -→ H the oriented graph obtained from G and a vertex t dominated by all these vertices. That is, for every -→ G by adding a vertex s domi-x ∈ V ( -→ G ), both sx and xt are arcs of -→ H . Arguing in the same way as in the previous item, -→ G admits an oriented k-total-coloring if and only if -→ H admits an oriented (k + 2)-total-coloring.
	• We finally consider the problem OTC * k+3 . This time, to obtain	-→ H from	-→ G , we just proceed as
	in the previous By similar arguments as earlier, -→ G admits an oriented k-total-coloring if and only if -→ H admits an oriented (k + 3)-total-coloring. Note that -→ H , here, has neither sources nor sinks.

  Thus, there cannot exist a homomorphism τ : T (

	-→ A ) → C of length at least g satisfying χ o ( -→ T 6 where τ (u 1 ) = x. -→ -→ C ) = 6. For every vertex A to the oriented graph, and identify u with the vertex u 1 of that Now consider an oriented cycle u of -→ C , add a new copy -→ A u of -→ new -→ A . Let us denote by -→ B the resulting oriented graph (whose girth is still at least g). Let τ : T ( -→ B ) → -→ T 6 . Since χ o (C) = 6, one of the vertices u of -→ C must satisfy τ (u) = x.
	Consider now the restriction of τ to

Throughout this work, the term graph refers to a simple undirected graph.

The authors were partly supported by ANR project HOSIGRA (ANR-17-CE40-0022), and by IFCAM project "Applications of graph homomorphisms" (MA/IFCAM/18/39).

The last gadget we need is the vertex gadget -→ V , depicted in Figure 6. Note that -→ V is obtained from the target gadget ----→ G target by attaching some structure to the vertices a and d. Besides, -→ V has two particular vertices, a strong vertex (denoted s in the figure), and a weak one (denoted w).

Note that this gadget is obtained by adding directed paths to

Proof. Note that it suffices to prove the first two items, as reversing the direction of all arcs of -→ T swaps weak and strong colors. To this end, it suffices to apply several times one of the following observations. Assume τ (s i ) is weak. Then τ (s i s i+1 ) and τ (s i+1 ) lie in {τ (s i )+1, τ (s i )+2, τ (s i )+3}, but s i s i+1 flows to s i+1 and hence we can have neither τ (s i s i+1 ) = τ (s i ) + 3 nor τ (s i+1 ) = τ (s i ) + 1. Hence, we have τ (s i s i+1 ) ∈ {τ (s i ) + 1, τ (s i ) + 2} and τ (s i+1 ) ∈ {τ (s i ) + 2, τ (s i ) + 3}. Otherwise, if τ (s i ) is strong, then by the same argument we must get τ (s i s i+1 ) = τ (s i ) + 1 and τ (s i+1 ) = τ (s i ) + 2.

We may now state the desired properties of -→ V .

Lemma 5.6.

) is good. Conversely, for every good pair (c, c ), there exists a -→ T -total-coloring τ of -→ V where:

• τ (w) = c and τ (s) = c ;

• the only arc xw verifies τ (xw) = c -1;

• the only arc sx verifies τ (sx) = c + 1.

Proof. Let τ be an oriented 6-total-coloring of -→ V . By Lemma 5.4, since

T -total-coloring. In particular, τ (a) = 0 and τ (d) = 3. Now, since a and s are joined by a directed 4-path, and similarly for w and d, by Lemma 5.5 we deduce that τ (s) ∈ {2, 3, 4} is strong and τ (w) ∈ {0, 1, 5} is weak. Moreover, we have:

• If τ (s) ∈ {2, 3}, then, because ws is an arc, we must have τ (s)-τ (w) ∈ {2, 3}. By Lemma 5.5 applied to the directed 4-path linking s to w, we must have τ (w) -τ (s) ∈ {2, 3}. This implies that we must have τ (w) = τ (s) + 3.