论文标题
特殊Digraphs的无环着色
Acyclic coloring of special digraphs
论文作者
论文摘要
有向图G =（V，e）的无环r颜色是顶点集V到R cyclic集中的分区。有向图G的二分法数是最小的R，因此G可以允许无环的R颜色。对于对称挖掘图，二分法数等于基础无向图的众所周知的色数。这使我们能够将W [1] - hard度和下限延续到通过Clique Width参数为二分法数问题的二分法问题的运行时间。我们介绍了第一种多项式时间算法，用于在恒定定向较大宽度的挖出术上针对无环着色问题。从参数化的角度来看，我们的算法表明，当通过定向的clique宽度进行参数化时，二分法数问题在XP中，并扩展了该问题的唯一已知的结构参数化。此外，我们在Monadic二阶逻辑中应用确定性，以表明当通过有向的集团宽度和R参数化时，二分法数问题在FPT中。 对于定向的共编是有向元素2的一类Digraphs，我们甚至显示了用于计算二分法数的线性时间解决方案。此外，我们得出的结论是，指示的共同雕像和所考虑的概括导致了完美的挖掘者的子类。对于定向的仙人掌森林，这是一组定向树宽度1的挖掘物，我们得出了二分法数为2的上限2，我们表明可以在线性时间内计算最佳的无环着色。
An acyclic r-coloring of a directed graph G=(V,E) is a partition of the vertex set V into r acyclic sets. The dichromatic number of a directed graph G is the smallest r such that G allows an acyclic r-coloring. For symmetric digraphs the dichromatic number equals the well-known chromatic number of the underlying undirected graph. This allows us to carry over the W[1]-hardness and lower bounds for running times of the chromatic number problem parameterized by clique-width to the dichromatic number problem parameterized by directed clique-width. We introduce the first polynomial-time algorithm for the acyclic coloring problem on digraphs of constant directed clique-width. From a parameterized point of view our algorithm shows that the Dichromatic Number problem is in XP when parameterized by directed clique-width and extends the only known structural parameterization by directed modular width for this problem. Furthermore, we apply defineability within monadic second order logic in order to show that Dichromatic Number problem is in FPT when parameterized by the directed clique-width and r. For directed co-graphs, which is a class of digraphs of directed clique-width 2, and several generalizations we even show linear time solutions for computing the dichromatic number. Furthermore, we conclude that directed co-graphs and the considered generalizations lead to subclasses of perfect digraphs. For directed cactus forests, which is a set of digraphs of directed tree-width 1, we conclude an upper bound of 2 for the dichromatic number and we show that an optimal acyclic coloring can be computed in linear time.
