论文标题
B-coloring通过集团宽度参数
b-Coloring Parameterized by Clique-Width
论文作者
论文摘要
我们为在恒定宽度宽度的图表上提供了多项式时间算法。这统一并扩展了几乎所有以前已知的多项式时间结果，并在坎波斯和席尔瓦[Algorithmica，2018]和Bonomo等提出的答案中答案。 [Graphs Combin。，2009]。这构成了有关此问题的结构参数化的第一个结果。我们表明，当通过一般图上的顶点封面编号和弦图上的顶点封面编号参数化时，问题是fpt，当通过颜色数参数化时。此外，我们观察到，可以对有界集团宽度图的算法进行调整以在同一运行时绑定的秋季着色问题上解决秋季着色问题。在指数时间假设下，基于集团宽度的算法的运行时间很紧。
We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by Campos and Silva [Algorithmica, 2018] and Bonomo et al. [Graphs Combin., 2009]. This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is FPT when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the Fall Coloring problem within the same runtime bound. The running times of the clique-width based algorithms for b-Coloring and Fall Coloring are tight under the Exponential Time Hypothesis.
