In this paper we consider colorings of oriented graphs, i.e. digraphs without cycles of length 2. Given some oriented graph $G=(V,E)$, an oriented $r$-coloring for $G$ is a partition of the vertex set $V$ into $r$ independent sets, such that all the arcs between two of these sets have the same direction. The oriented chromatic number of $G$ is the smallest integer $r$ such that $G$ permits an oriented $r$-coloring. In this paper we consider the Oriented Chromatic Number problem on classes of recursively defined oriented graphs. Oriented co-graphs (short for oriented complement reducible graphs) can be recursively defined defined from the single vertex graph by applying the disjoint union and order composition. This recursive structure allows to compute an optimal oriented coloring and the oriented chromatic number in linear time. We generalize this result using the concept of perfect orderable graphs. Therefore, we show that for acyclic transitive digraphs every greedy coloring along a topological ordering leads to an optimal oriented coloring. Msp-digraphs (short for minimal series-parallel digraphs) can be defined from the single vertex graph by applying the parallel composition and series composition. We prove an upper bound of $7$ for the oriented chromatic number for msp-digraphs and we give an example to show that this is bound best possible. We apply this bound and the recursive structure of msp-digraphs to obtain a linear time solution for computing the oriented chromatic number of msp-digraphs. In order to generalize the results on computing the oriented chromatic number of special graph classes, we consider the parameterized complexity of the Oriented Chromatic Number problem by so-called structural parameters, which are measuring the difficulty of decomposing a graph into a special tree-structure
翻译:在本文中,我们考虑向导图形的颜色颜色,即没有长度周期的向导图形的颜色值。 2 在某种向导图形 $G=(V,E)$($G$) 的情况下,向导的美元颜色值是将顶端设定为美元美元独立的数据集的分割区, 使这两组之间的所有弧线都具有相同的方向。 向导色数$是最小整数的整数, 美元允许向导 $r$- 彩色。 在本文中, 我们考虑在循环定义的向导图表结构的类别中, 向导的花色数字数字值问题。 向导的双向双向双向双向双向双向双向双向双向双向双向双向双向双向双向双向双向双向双向双向双向双向每个螺旋式的颜色结构值, 向上向每个螺旋向方向的变色序图层显示一个最细数。