b-Coloring Parameterized by Clique-Width
b-Coloring Parameterized by Clique-Width
复制标题
DOI：
10.4230/lipics.stacs.2021.43
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
L. Jaffke;Paloma T. Lima;D. Lokshtanov
中科院分区：
文献类型：
--
作者：
L. Jaffke;Paloma T. Lima;D. Lokshtanov
本文给出了一个多项式时间算法来求解常宽度图的b-着色问题。这统一并扩展了几乎所有先前已知的关于图类的多项式时间结果，并回答了Campos和Silva（Graphica 80（1），104-115，2018）和Bonomo等人（Graphs and Combinatorics 25（2），153-167，2009）提出的开放性问题。这构成了这个问题的结构参数化的第一个结果。我们表明，问题是$$\textsf{FPT}$$ FPT时，参数化的顶点覆盖数一般的图形，和弦图时，参数化的颜色数。此外，我们观察到，我们的算法的有界candle宽度的图形可以适应解决秋季着色问题在相同的运行时间范围内。在指数时间假设下，基于candle-width的$$B$$ B -着色和Fall着色算法的运行时间是紧的。
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 80(1), 104–115, 2018) and Bonomo et al. (Graphs and Combinatorics 25(2), 153–167, 2009). This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is $$\textsf{FPT}$$ 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$$ b -Coloring and Fall Coloring are tight under the Exponential Time Hypothesis.