论文标题
紧密绑定的无冲突着色，距离群集的距离
A Tight Bound for Conflict-free Coloring in terms of Distance to Cluster
论文作者
论文摘要
给定无向图$ g =（v，e）$，与开放式邻域（CFON着色）的无冲突着色是顶点着色，使每个顶点在其开放式邻域中都具有独特的彩色顶点。这种着色所需的最低颜色数是$ g $的CFON色度数，由$χ_{on}（g）$表示。 在先前的工作[WG 2020]中，我们显示了上限$χ_{on}（g）\ leq dc（g） + 3 $，其中$ dc（g）$表示$ g $的群集参数的距离。在本文中，我们获得了$χ_{on}（g）\ leq dc（g） + 1 $的改进上限。我们还展示了$χ_{on}（g）> dc（g）$的图表家庭，从而证明我们的上限很紧。
Given an undirected graph $G = (V,E)$, a conflict-free coloring with respect to open neighborhoods (CFON coloring) is a vertex coloring such that every vertex has a uniquely colored vertex in its open neighborhood. The minimum number of colors required for such a coloring is the CFON chromatic number of $G$, denoted by $χ_{ON}(G)$. In previous work [WG 2020], we showed the upper bound $χ_{ON}(G) \leq dc(G) + 3$, where $dc(G)$ denotes the distance to cluster parameter of $G$. In this paper, we obtain the improved upper bound of $χ_{ON}(G) \leq dc(G) + 1$. We also exhibit a family of graphs for which $χ_{ON}(G) > dc(G)$, thereby demonstrating that our upper bound is tight.
