# Oriented Coloring on Recursively Defined Digraphs
## 4 Graph Coloring on Recursively Defined Digraphs
### Oriented Graph Coloring for Oriented Graphs  
Oriented graph coloring has not yet been considered for recursively defined graphs, though it has been analyzed for some graph operations. In this section we show results of oriented graph coloring on some graph operations and provide algorithms for recursively defined oriented graph classes. This will also be useful for the following section. First, we give some results on the oriented graph coloring for general recursively defined oriented graphs. These results will be very useful to prove our results for oriented co-graphs in the next section. **Lemma 5**. : _Let \(G_{1},\ldots,G_{k}\) be \(k\) vertex-disjoint oriented graphs. Then the following equations holds:_  
1. \(\chi_{o}(G_{1}\oplus\bullet)=\chi_{o}(G_{1})\)__
2. \(\chi_{o}(G_{1}\oplus\ldots\oplus G_{k})\geq\max(\chi_{o}(G_{1}),\ldots,\chi_{o} (G_{k}))\)__
3. \(\chi_{o}(G_{1}\oslash\ldots\oslash G_{k})=\chi_{o}(G_{1})+\ldots+\chi_{o}(G_{k})\)__  
**Proof. **  
1. \(\chi_{o}(G_{1}\oplus\bullet)\leq\chi_{o}(G_{1})\)__  
Since no new arcs are inserted \(G_{1}\) can keep its colors. The added isolated vertex gets a color of \(G_{1}\) in order to obtain a valid coloring for \(G_{1}\oplus\bullet\). \(\chi_{o}(G_{1}\oplus\bullet)\geq\chi_{o}(G_{1})\)__This relation holds by Lemma 4, since \(G_{1}\) is an induced subdigraph of \(G_{1}\oplus\bullet\). 2. \(\chi_{o}(G_{1}\oplus\ldots\oplus G_{k})\geq\max(\chi_{o}(G_{1}),\ldots,\chi_{o}( G_{k}))\) Since the digraphs \(G_{1},\ldots,G_{k}\) are induced subdigraphs of digraph \(G_{1}\oplus\ldots\oplus G_{k}\), all values \(\chi_{o}(G_{1}),\ldots,\chi_{o}(G_{k})\) lead to a lower bound for the number of necessary colors of the combined graph by Lemma 4. 3. \(\chi_{o}(G_{1}\oslash\ldots\oslash G_{k})\leq\chi_{o}(G_{1})+\ldots+\chi_{o}(G_ {k})\) For \(1\leq i\leq k\) let \(G_{i}=(V_{i},A_{i})\) and \(c_{i}:V_{i}\rightarrow\{1,\ldots,\chi_{o}(G_{i})\}\) a coloring for \(G_{i}\). For \(G_{1}\oslash\ldots\oslash G_{k}=(V,A)\) we define a mapping \(c:V\rightarrow\{1,\ldots,\sum_{j=1}^{k}\chi_{o}(G_{i})\}\) as follows. \[c(v)=\left\{ \begin{array}{ll}c_{1}(v)&\text{ if }v\in V_{G_{1}}\\ c_{i}(v)+\sum_{j=1}^{i-1}\chi_{o}(G_{i})&\text{ if }v\in V_{G_{i}},\;2\leq i \leq k.\end{array} \right.\] The mapping \(c\) satisfies the definition of an oriented coloring, because no two adjacent vertices from \(G_{i}\), \(1\leq i\leq k\), have the same color by assumption and by definition of \(c\). For \(1\leq i\
eq j\leq k\) a vertex of \(G_{i}\) and a vertex of \(G_{j}\) are always adjacent, but never colored equally by definition of \(c\). Further, the arcs between two color classes of every \(G_{i}\), \(1\leq i\leq k\), have the same direction by definition of \(c\). For \(1\leq i\
eq j\leq k\) the arcs between a color class of \(G_{i}\) and a color class of \(G_{j}\) have the same direction by definition of the order operation. \(\chi_{o}(G_{1}\oslash\ldots\oslash G_{k})\geq\chi_{o}(G_{1})+\ldots+\chi_{o}(G_ {k})\) Since every \(G_{i}\), \(1\leq i\leq k\), is an induced subdigraph of the combined graph, all values \(\chi_{o}(G_{1}),\ldots,\chi_{o}(G_{k})\) lead to a lower bound for the number of necessary colors of the combined graph by Lemma 4. Further, the order operations implies that for every \(1\leq i\
eq j\leq k\) no vertex in \(G_{i}\) can be colored in the same way as a vertex in \(G_{j}\). Thus, \(\chi_{o}(G_{1})+\ldots+\chi_{o}(G_{k})\) leads to a lower bound for the number of necessary colors of the combined graph. This shows the statements of the lemma. By Lemma 5, we can solve oriented coloring for oriented simple co-graphs and thus, also for subclasses, such as oriented threshold graphs and transitive tournaments, in linear time. Proposition 2: _Let \(G\) be an oriented simple co-graph. Then, it holds that \(\chi_{o}(G)=\chi(und(G))=\omega(und(G))\) and all values can be computed in linear time._  
It is not easy to generalize these results to oriented co-graphs.