# Oriented Coloring on Recursively Defined Digraphs
## 4 Graph Coloring on Recursively Defined Digraphs
### Oriented Graph Coloring for Oriented Co-Graphs  
In order to solve OCN restricted to oriented co-graphs \(G\) we created a procedure, which is shown in Algorithm 1. The method traverses a canonical di-co-tree \(T\) for \(G\) using a depth-first search, such that for every inner vertex the children are visited from left to right. For every inner vertex \(u\) of \(T\), we store two values in\([u]\) and out\([u]\). These values ensure that the vertices of \(G\), corresponding to the leaves of the subtree, rooted at \(u\) will we labeled by labels \(\ell\), such that in\([u]\leq\ell\leq\text{out}[u]\). For every leaf vertex \(u\) of \(T\), we additionally store the label of the corresponding vertex of \(G\) in color\([u]\). These values lead to an optimal oriented coloring of \(G\) by the next theorem. ```
procedureLabel\((G,u,i)\) if(\(u\) is a leaf of \(T\)) { \(\text{color}[u]=i\); \(\text{in}[u]=i\); \(\text{out}[u]=i\); } else{ \(\text{in}[u]=i\); \(\text{out}[u]=0\); for all children\(v\) of \(u\) from left to right do { \(j=\)Label\((G,v,i)\); if(out\([u]<j\)) \(\text{out}[u]=j\); if(\(u\) corresponds to a disjoint union) \(i=\text{in}[u]\); else\(\blacktriangleright\)\(u\) corresponds to an order operation \(i=\text{out}[v]+1\); }
```  
**Algorithm 1**Computing an oriented coloring for an oriented co-graph. **Theorem 3**: _Let \(G\) be an oriented co-graph. Then, an optimal oriented coloring for \(G\) and \(\chi_{o}(G)\) can be computed in linear time._  
Let \(G=(V,A)\) be an oriented co-graph. Using the method of [17] we can build a di-co-tree \(T\) with root \(r\) for \(G\) in linear time. Further by Lemma 2, we can assume that \(T\) is a canonical di-co-tree. For some node \(u\) of \(T\) we define by \(T_{u}\) the subtree of \(T\) which is rooted at \(u\) and by \(G_{u}\) the subgraph of \(G\) which is defined by \(T_{u}\). Obviously, for every vertex \(u\) of \(T\) the tree \(T_{u}\) is a di-co-tree for the digraph \(G_{u}\) which is also an oriented co-graph. Next, we verify that procedure Label\((G,r,1)\), shown in Algorithm 1, returns the value \(\chi_{o}(G)\) and computes an oriented coloring for \(G\) within array color\([u]\). Therefore, we recursively show for every vertex \(u\) of \(T\) that after performing Label\((G,u,i)\) for all leaves \(u\) of \(T_{u}\) the value color\([u]\) leads to an oriented coloring of \(G_{u}\) using the colors \(\{i=\text{in}[u],\dots,\text{out}[u]\}\) (Please note that using colors starting at values greater than \(1\) is not a contradiction to Definition 3.) and the value out\([u]-\text{in}[u]+1\) leads to the oriented chromatic number of \(G_{u}\). We distinguish the following three cases depending on the type of operation corresponding to the vertices \(u\) of \(T\). * If \(u\) is a leaf of \(T\), then color\([u]=\text{out}[u]=\text{in}[u]\) by the algorithm leads to an oriented coloring of \(G_{u}\). Further, out\([u]-\text{in}[u]+1=1\), which obviously corresponds to the oriented chromatic number of \(G_{u}\). * Let \(u\) be an inner vertex of \(T\) which corresponds to an order operation and \(u_{1},\dots,u_{\ell}\) are the children of \(u\) in \(T\). We already know that the oriented colorings of \(G_{u_{i}},1\leq i\leq\ell\), are feasible. Further, for \(1\leq i\
eq j\leq\ell\), the algorithm's way of working ensures that a vertex from \(G_{u_{i}}\) and a vertex from \(G_{u_{j}}\) are never colored equally in \(G_{u}\). For \(1\leq i\
eq j\leq\ell\), the arcs between a color class of \(G_{u_{i}}\) and a color class of \(G_{u_{j}}\) have the same direction by the definition of the order operation. By the algorithm, value \(\operatorname{out}[u]-\operatorname{in}[u]+1\) is equal to \(\sum_{i=1}^{\ell}\chi_{o}(G_{u_{i}})\). By Lemma 5, we conclude that \(\operatorname{out}[u]-\operatorname{in}[u]+1\) is equal to \(\chi_{o}(G_{i_{1}}\oslash\ldots\oslash G_{i_{\ell}})=\chi_{o}(G_{u})\). * Let \(u\) be an inner vertex of \(T\) which corresponds to a disjoint union operation and \(u_{1},\ldots,u_{\ell}\) are the children of \(u\) in \(T\).