# Oriented Coloring on Recursively Defined Digraphs
## 4 Graph Coloring on Recursively Defined Digraphs
### Oriented Graph Coloring for Oriented Co-Graphs
We already know that the oriented colorings of \(G_{u_{i}},1\leq i\leq\ell\), are feasible. Since a disjoint union operation does not create any arcs, no two adjacent vertices have the same color in \(G_{u}\). Further, our method ensures that for every arc \((u,v)\) in \(G\) it holds that \(\operatorname{color}[u]<\operatorname{color}[v]\). Thus, all arcs between two color classes in \(G_{u}\) have the same direction. By the algorithm, value \(\operatorname{out}[u]-\operatorname{in}[u]+1\) is equal to \(\max(\chi_{o}(G_{1}),\ldots,\chi_{o}(G_{\ell}))\). By Lemma 5, we conclude that \(\operatorname{out}[u]-\operatorname{in}[u]+1\leq\chi_{o}(G_{1}\oplus\ldots \oplus G_{\ell})=\chi_{o}(G_{u})\). The relation \(\operatorname{out}[u]-\operatorname{in}[u]+1\geq\chi_{o}(G_{1}\oplus\ldots \oplus G_{\ell})=\chi_{o}(G_{u})\) holds by the feasibility of our oriented coloring. By applying the invariant for \(u=r\), the statements of the theorem follow. **Example 3**. : _We illustrate the method given in Algorithm 1 by computing an oriented coloring for the oriented co-graph \(G\), which is given by the canonical di-co-tree \(T\) of Figure 3. On the left of each vertex \(u\) of \(T\), the values \(\operatorname{in}[u]\) and \(\operatorname{out}[u]\) are given. An optimal oriented coloring for \(G\) is given in blue letters below the leaves of \(T\). The root \(r\) of \(T\) leads to \(\chi_{o}(G)=\operatorname{out}[r]=5\)._  
Next, we can improve the result of Lemma 5 (2) for oriented co-graphs. **Corollary 1**. : _Let \(G_{1},\ldots,G_{k}\) be \(k\) vertex-disjoint oriented co-graphs. Then, it holds that_  
\[\chi_{o}(G_{1}\oplus\ldots\oplus G_{k})=\max(\chi_{o}(G_{1}),\ldots,\chi_{o}( G_{k})).\]  
Proof. : Let \(G=G_{1}\oplus\ldots\oplus G_{k}\) be an oriented co-graph and \(T\) be a di-co-tree with root \(r\) for \(G\). The method given in Algorithm 1 computes an oriented coloring using \(\chi_{o}(G)=\chi_{o}(G_{1}\oplus\ldots\oplus G_{k})\) colors. Further, the proof of Theorem 3 shows that \(\chi_{o}(G_{1}\oplus\ldots\oplus G_{k})=\max(\chi_{o}(G_{1}),\ldots,\chi_{o}( G_{k}))\). Figure 3: Canonical di-co-tree \(T\) for oriented co-graph \(G\). **Corollary 2**. : _Let \(G\) be an oriented co-graph. The following properties are equivalent:_  
1. \(G\) _is an oriented clique._
2. \(G\) _has a di-co-tree, which does not use any disjoint union operation._
3. \(G\) _is a transitive tournament._  
Further characterizations for transitive tournaments and oriented co-graphs, which are oriented cliques, can be found in [23] (Chapter 9). As mentioned in Observation 2, oriented coloring of an oriented graph \(G\) can be characterized by the existence of homomorphisms to tournaments. These tournaments are not necessarily transitive and \(G\) is not necessarily homomorphically equivalent to some tournament. For oriented co-graphs we can show a deeper result. **Corollary 3**. : _There is an oriented \(k\)-coloring of an oriented co-graph \(G\) if and only if there is a homomorphism from \(G\) to some transitive tournament \(\overrightarrow{T_{k}}\) on \(k\) vertices. Further, the oriented chromatic number of an oriented co-graph \(G\) is the minimum number \(k\), such that \(G\) is homomorphically equivalent with the transitive tournament \(\overrightarrow{T_{k}}\)._  
Proof. : Within an oriented co-graph \(G=(V,A)\) the color classes \(V_{1},\ldots,V_{k}\) of an oriented \(k\)-coloring define a transitive tournament \(\overrightarrow{T_{k}}=(\{V_{1},\ldots,V_{k}\},\{(V_{i},V_{j})\mid v_{i}\in V_ {i},v_{j}\in V_{j},(v_{i},v_{j})\in A\})\). If \(k=\chi_{o}(G)\), then there is a homomorphism from \(\overrightarrow{T_{k}}\) to \(G\).