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 \chi_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.
翻译:图形 G 的星彩色是一个适当的顶点颜色, 使四个顶点上的每条路径至少使用三种不同的颜色。 G 星彩色所需的最低颜色数量称为星色数, 由\ chi_ s( G) 表示。 从一个图形 G 和正整数 k 来看, STAR COLOING Problem 询问$G$是否有一个星色, 使用最多 k 的颜色。 这个问题甚至存在于诸如双面图解等限制的图形类别上, 也是NP- 完整的 。 在本文中, 我们从参数化复杂角度开始对 Star COLOLING 进行研究 。 我们显示 STAR COLORING 是固定参数, 当参数化为 (a) 社区多样性, (b) 双覆盖, 以及 (c) 组合参数 圆线和颜色数 。