标题： 距离到聚类的冲突-free着色的紧界 显示英文标题

标题： A Tight Bound for Conflict-free Coloring in terms of Distance to Cluster

摘要： 给定一个无向图$G = (V,E)$，相对于开邻域的冲突自由着色（CFON着色）是一种顶点着色，使得每个顶点在其开邻域中都有一个独特着色的顶点。 进行这种着色所需的最小颜色数是$G$的 CFON色数，记为$\chi_{ON}(G)$。 在之前的工作 [WG 2020] 中，我们证明了上界$\chi_{ON}(G) \leq dc(G) + 3$，其中$dc(G)$表示$G$的聚类距离参数。 在本文中，我们得到了改进的上界$\chi_{ON}(G) \leq dc(G) + 1$。 我们还展示了一类图，其中$\chi_{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 $\chi_{ON}(G)$. In previous work [WG 2020], we showed the upper bound $\chi_{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 $\chi_{ON}(G) \leq dc(G) + 1$. We also exhibit a family of graphs for which $\chi_{ON}(G) > dc(G)$, thereby demonstrating that our upper bound is tight.