论文标题
有效地计算定向的递归定义的挖掘物
Efficient computation of the oriented chromatic number of recursively defined digraphs
论文作者
论文摘要
在本文中，我们考虑了定向图的颜色，即没有循环2的挖掘图。给定一些方向的图形$ g =（v，e）$，是$ g $的定向$ r $ $颜色的分区是$ r $ $ r $独立套件的$ v $的分区，以便在这些方向之间所有相同的方向之间的所有arc之间。 $ g $的定向色度是最小的整数$ r $，因此$ g $允许定向的$ r $颜色。 在本文中，我们考虑了递归定义的面向图的类别的定向色数问题。可以通过应用不连接的联合和秩序组成来递归定义定义的定义的定义的定义，可以递归定义了定义的定义。这种递归结构允许在线性时间内计算最佳的面向着色和定向色数。我们使用完美的订购图的概念概括了此结果。因此，我们表明，对于无环的透射式挖掘，沿拓扑排序的每种贪婪的着色都会导致最佳的面向着色。可以通过应用并行组成和串联组成来从单个顶点图定义MSP-Dipraphs（最小串联 - 平行挖掘图）。我们证明，对于MSP-Digraphs的定向色号，我们的上限为$ 7 $，我们举例说明这是最好的。我们应用了MSP-偏边的这种结合和递归结构，以获得用于计算定向色数MSP-传输数量的线性时间解决方案。 为了概括计算特殊图类别的定向色数的结果，我们通过所谓的结构参数考虑了定向色度数问题的参数化复杂性，这些结构参数正在测量将图分解为特殊树结构的难度
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
