论文标题
关于恒星着色的结构参数化
On Structural Parameterizations of Star Coloring
论文作者
论文摘要
图G的星形着色是适当的顶点着色，因此四个顶点上的每个路径至少都使用三种不同的颜色。这种G的恒星着色所需的最小颜色数量称为星形数字，用χ_s（G）表示。给定图G和一个正整数K，恒星着色问题询问$ g $是否具有最多使用K颜色的星形着色。即使在诸如双方图形之类的受限制的图类别上，此问题也是NP完整的。 在本文中，我们从参数化的复杂性角度开始研究恒星着色。我们表明，当通过（a）邻域多样性，（b）双胞胎覆盖和（c）组合参数集合宽度和颜色的数量进行参数化时，恒星着色是固定参数。
A Star Coloring of a graph G is a proper vertex coloring such that every path on four vertices uses at least three distinct colors. The minimum number of colors required for such a star coloring of G is called star chromatic number, denoted by χ_s(G). Given a graph G and a positive integer k, the STAR COLORING PROBLEM asks whether $G$ has a star coloring using at most k colors. This problem is NP-complete even on restricted graph classes such as bipartite graphs. In this paper, we initiate a study of STAR COLORING from the parameterized complexity perspective. We show that STAR COLORING is fixed-parameter tractable when parameterized by (a) neighborhood diversity, (b) twin-cover, and (c) the combined parameters clique-width and the number of colors.
