# Oriented Coloring on Recursively Defined Digraphs
## 3 Oriented Co-Graphs  
Oriented colorings are defined on oriented graphs, which are digraphs with no bidirected edges. Therefore we introduce oriented co-graphs by omitting the series operation from the definition of directed co-graphs, as given in [10]. **Definition 2** (Oriented Co-Graphs). : _The class of oriented co-graphs is recursively defined as follows._  
1. _Every digraph on a single vertex_ \((\{v\},\emptyset)\)_, denoted by_ \(\bullet\)_, is an oriented co-graph._
2. _If_ \(G_{1},\ldots,G_{k}\) _are_ \(k\) _vertex-disjoint oriented co-graphs, then_ 1. \(G_{1}\oplus\ldots\oplus G_{k}\) _and_ 2. \(G_{1}\oslash\ldots\oslash G_{k}\) _are oriented co-graphs._  
The class of oriented co-graphs was already analyzed by [PERSON] in [11] and [3] (Section 5) using the notation of _transitive series parallel (TSP) digraphs_. A digraph \(G=(V,A)\) is called _transitive_, if for every pair \((u,v)\in A\) and \((v,w)\in A\) of arcs with \(u\
eq w\) the arc \((u,w)\) also belongs to \(A\). **Theorem 1** ([3]). : _A graph \(G\) is a co-graph if and only if there exists an orientation \(G^{\prime}\) of \(G\), such that \(G^{\prime}\) is an oriented co-graph._  
A di-co-tree \(T\) is _canonical_ if on every path from the root to the leaves of \(T\), the labels disjoint union and order operation strictly alternate. Since the disjoint union \(\oplus\) and the order composition \(\oslash\) are associative, we always can assume canonical di-co-trees. **Lemma 2**. : _Let \(G\) be an oriented co-graph and \(T\) be a di-co-tree for \(G\). Then, \(T\) can be transformed in linear time into a canonical di-co-tree for \(G\)._  
The recursive definitions of oriented and undirected co-graphs lead to the following observation. **Observation 1**. : _For every oriented co-graph \(G\) the underlying undirected graph \(\mathit{und}(G)\) is a co-graph._  
Figure 2: The eight forbidden induced subdigraphs for directed co-graphs. The reverse direction of this observation only holds under certain conditions, see Theorem 2. By \(\overleftrightarrow{P_{2}}=(\{v_{1},v_{2}\},\{(v_{1},v_{2}),(v_{2},v_{1})\})\) we denote the complete biorientation of a path on two vertices. **Lemma 3**: _Let \(G\) be a digraph, such that \(G\in\text{Free}(\{\overleftrightarrow{P_{2}},D_{1},D_{5}\})\). Then, it holds that \(G\) is transitive._  
Let \((u,v),(v,w)\in A\) be two arcs of \(G=(V,A)\). Since \(G\in\text{Free}(\{\overleftrightarrow{P_{2}}\})\), we know that \((v,u),(w,v)\
ot\in A\). Further, since \(G\in\text{Free}(\{D_{1},D_{5}\})\), we know that \(u\) and \(w\) are connected either only by \((u,w)\in A\) or by \((u,w)\in A\) and \((w,u)\in A\), which implies that \(G\) is transitive. Oriented co-graphs can be characterized by forbidden subdigraphs as follows. Let \(G\) be a digraph. The following properties are equivalent:  
1. \(G\) is an oriented co-graph. 2. \(G\in\text{Free}(\{D_{1},D_{5},D_{8},\overleftrightarrow{P_{2}}\})\). 3. \(G\in\text{Free}(\{D_{1},D_{5},\overleftrightarrow{P_{2}}\})\) and \(und(G)\in\text{Free}(\{P_{4}\})\). 4. \(G\in\text{Free}(\{D_{1},D_{5},\overleftrightarrow{P_{2}}\})\) and \(und(G)\) is a co-graph. 5. \(G\) has directed NLC-width \(1\) and \(G\in\text{Free}(\{\overleftrightarrow{P_{2}}\})\). 6. \(G\) has directed clique-width at most \(2\) and \(G\in\text{Free}(\{\overleftrightarrow{P_{2}}\})\). 7. \(G\) is transitive and \(G\in\text{Free}(\{\overleftrightarrow{P_{2}},D_{8}\})\). \((1)\Rightarrow(2)\) If \(G\) is an oriented co-graph, then \(G\) is a directed co-graph and by [17] it holds that \(G\in\text{Free}(\{D_{1},\ldots,D_{8}\})\). Furthermore, \(G\in\text{Free}(\{\overleftrightarrow{P_{2}}\})\) because of the missing series composition. This leads to \(G\in\text{Free}(\{D_{1},D_{5},D_{8},\overleftrightarrow{P_{2}}\})\). \((2)\Rightarrow(1)\) If \(G\in\text{Free}(\{D_{1},D_{5},D_{8},\overleftrightarrow{P_{2}}\})\), then \(G\in\text{Free}(\{D_{1},\ldots,D_{8}\})\) and is \(G\) a directed co-graph.