# Oriented Coloring on Recursively Defined Digraphs
## 4 Graph Coloring on Recursively Defined Digraphs  
### Oriented Graph Coloring Problem  
Oriented graph coloring has been introduced by [PERSON] [4] in 1994. Most results on this problem consider orientations of undirected graphs. Now, we consider oriented graph coloring on recursively defined oriented graph classes.  
[Oriented Graph Coloring [4]] An oriented \(k\)-coloring of an oriented graph \(G=(V,A)\) is a mapping \(c:V\rightarrow\{1,\ldots,k\}\), such that:  
* \(c(u)\
eq c(v)\) for every \((u,v)\in A\)
* \(c(u)\
eq c(y)\) for every two arcs \((u,v)\in A\) and \((x,y)\in A\) with \(c(v)=c(x)\)  
The oriented chromatic number of \(G\), denoted by \(X_{o}(G)\), is the smallest \(k\), such that \(G\) has an oriented \(k\)-coloring. The vertex sets \(V_{i}=\{v\in V\mid c(v)=i\}\), \(1\leq i\leq k\), divide a partition of \(V\) into so called color classes.  
For two oriented graphs \(G_{1}=(V_{1},A_{1})\) and \(G_{2}=(V_{2},A_{2})\) a _homomorphism_ from \(G_{1}\) to \(G_{2}\), \(G_{1}\to G_{2}\) for short, is a mapping \(h:V_{1}\to V_{2}\), such that \((u,v)\in A_{1}\) implies that \((h(u),h(v))\in A_{2}\). The orientedgraphs \(G_{1}\) and \(G_{2}\) are _homomorphically equivalent_, if there is a homomorphism from \(G_{1}\) to \(G_{2}\) and one from \(G_{2}\) to \(G_{1}\). A homomorphism from \(G_{1}\) to \(G_{2}\) can be regarded as an oriented coloring of \(G_{1}\) that uses the vertices of \(G_{2}\) as colors classes. This leads to equivalent definitions for oriented coloring and oriented chromatic number. There is an oriented \(k\)-coloring of an oriented graph \(G_{1}\) if and only if there is a homomorphism from \(G_{1}\) to some oriented graph \(G_{2}\) on \(k\) vertices. That is, the oriented chromatic number of \(G\) is the minimum number of vertices in an oriented graph \(G_{2}\), such that there is a homomorphism from \(G_{1}\) to \(G_{2}\). Obviously, \(G_{2}\) can be chosen as a tournament.  
**Observation 2**.: _There is an oriented \(k\)-coloring of an oriented graph \(G_{1}\) if and only if there is a homomorphism from \(G_{1}\) to some tournament \(G_{2}\) on \(k\) vertices. Further, the oriented chromatic number of \(G\) is the minimum number of vertices in a tournament \(G_{2}\), such that there is a homomorphism from \(G_{1}\) to \(G_{2}\)._  
**Lemma 4**.: _Let \(G\) be an oriented graph and \(H\) be a subdigraph of \(G\), then \(\chi_{o}(H)\leq\chi_{o}(G)\)._  
**Example 1**.: _For oriented paths and oriented cycles we know: \(\chi_{o}(\overrightarrow{P_{2}})=2\), \(\chi_{o}(\overrightarrow{P_{3}})=3\), \(\chi_{o}(\overrightarrow{C_{4}})=4\), \(\chi_{o}(\overrightarrow{C_{5}})=5\)._  
An oriented graph \(G=(V,A)\) is an _oriented clique_ (\(o\)-_clique_) if \(\chi_{o}(G)=|V|\). Thus all graphs given in Example 1 are oriented cliques.  
**Name**: Oriented Chromatic Number (OCN)
**Instance**: An oriented graph \(G=(V,A)\) and a positive integer \(c\leq|V|\).
**Question**: Is there an oriented \(c\)-coloring for \(G\)?  
If \(c\) is constant and not part of the input, the corresponding problem is denoted by \(\mathrm{OCN}_{c}\). Even for DAGs \(\mathrm{OCN}_{4}\) is NP-complete [5].  
The definition of oriented coloring is also used for undirected graphs. For an undirected graph \(G\) the maximum value \(\chi_{o}(G^{\prime})\) of all possible orientations \(G^{\prime}\) of \(G\) is considered. In this sense, every tree has oriented chromatic number at most 3. For several further graph classes there exist bounds on the oriented number. Among these are outerplanar graphs [6], planar graphs [7], and Halin graphs [8].