# Oriented Coloring on Recursively Defined Digraphs
## 1 Introduction  
Graph coloring is one of the basic problems in graph theory, which has already been considered in the 19 th century. A \(k\)-coloring for an undirected graph \(G\) is a \(k\)-labeling of the vertices of \(G\) such that no two adjacent vertices have the same label. The smallest \(k\) such that a graph \(G\) has a \(k\)-coloring is named the chromatic number of \(G\). As even the problem whether a graph has a \(3\)-coloring, is NP-complete, finding the chromatic number of an undirected graph is an NP-hard problem. However, there are many efficient solutions for the coloring problem on special graph classes, like chordal graphs [1], comparability graphs [2], and co-graphs [3]. Oriented coloring has been introduced much later by [PERSON] [4]. One could easily apply the definition of graph coloring to directed graphs, but as this would not take the direction of the arcs into account, this would not be very interesting. For such a definition, the coloring of a directed graph would be the coloring of the underlying undirected graph. Oriented coloring also considers the direction of the arcs. An oriented \(k\)-coloring of an oriented graph \(G=(V,A)\) is a partition of the vertex set \(V\) into \(k\) independent sets, such that all the arcs linking two of these subsets have the same direction. In the oriented chromatic number problem (OCN for short) there is given some oriented graph \(G\) and some integer \(c\) and one has to decide whether there is an oriented \(c\)-coloring for \(G\). Even the restricted problem, when \(c\) is constant and does not belong to the input (OCN\({}_{c}\) for short), is hard. OCN\({}_{4}\) is NP-complete even for DAGs [5], whereas the undirected problem is easy for trees. Right now, the definition of oriented coloring is mostly considered for undirected graphs. There the maximum value \(\chi_{o}(G^{\prime})\) of all possible orientations \(G^{\prime}\) of an undirected graph \(G\) is considered. For several special undirected graph classes the oriented chromatic number has been bounded. Among these are outerplanar graphs [6], planar graphs [7], and Halin graphs [8]. In [9], [PERSON] has shown an FPT-algorithm for OCN w.r.t. the parameter tree-width (of the underlying undirected graph). Further, he has shown that OCN is DET-hard (DET is the class of decision problems which are reducible in logarithmic space to the problem of computing the determinant of an integer valued \(n\times n\)-matrix.) for classes of oriented graphs, such that the underlying undirected class has bounded rank-width. Oriented coloring of special digraph classes seems not to be investigated up to now. The main reason is that the oriented chromatic number of the disjoint union of two oriented graphs can be larger than the maximum oriented chromatic number of the involved graphs (cf. Figure 1 and Example 2). In this paper, we consider the oriented coloring problem restricted to oriented co-graphs, which are obtained from directed co-graphs [10] by omitting the series operation. Oriented co-graphs were already analyzed by [PERSON] in [11] and [3] (Section 5) using the notation of transitive series parallel (TSP) digraphs. We give several characterizations for oriented co-graphs and show that for oriented co-graphs, the oriented chromatic number of the disjoint union of oriented graphs is equal to the maximum oriented chromatic number of the involved graphs. Further, we show that for every oriented graph the oriented chromatic number of the order composition of oriented graphs is equal to the sum of the oriented chromatic numbers of the involved graphs. To show this, we introduce an algorithm that computes an optimal oriented coloring and thus, the oriented chromatic number of oriented co-graphs in linear time. We also consider the longest oriented path problem on oriented co-graphs. It turns out that within oriented co-graphs the oriented chromatic number is equal to the length of a longest oriented path plus one. Further, we give a linear time algorithm for the graph isomorphism problem on oriented co-graphs.