论文标题
集团着色的结构参数化
Structural Parameterizations of Clique Coloring
论文作者
论文摘要
图形的集团颜色是其顶点的颜色分配，因此没有最大集团是单色的。我们启动了集团着色问题的结构参数化研究，该问题询问给定图是否具有$ q $颜色的集团着色。对于固定的$ q \ ge 2 $，我们给出了$ \ mathcal {o}^{\ star}（q^{tw}）$ - 时间算法，当输入图与其宽度宽度$ tw $的一个树分解一起给出时。我们通过强烈的指数时间假设下的匹配下限进行补充。我们进一步表明（当颜色的数量是无限的）集团着色是通过集团宽度参数化的。
A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether a given graph has a clique coloring with $q$ colors. For fixed $q \ge 2$, we give an $\mathcal{O}^{\star}(q^{tw})$-time algorithm when the input graph is given together with one of its tree decompositions of width $tw$. We complement this result with a matching lower bound under the Strong Exponential Time Hypothesis. We furthermore show that (when the number of colors is unbounded) Clique Coloring is XP parameterized by clique-width.
