Conflict-Free Coloring Bounds on Open Neighborhoods

Abstract

In an undirected graph $G$, a conflict-free coloring with respect to open neighborhoods (denoted by CFON coloring) is an assignment of colors to the vertices such that every vertex has a uniquely colored vertex in its open neighborhood. The minimum number of colors required for a CFON coloring of $G$ is the CFON chromatic number of $G$, denoted by $\chi_{ON}(G)$. The decision problem that asks whether $\chi_{ON}(G) \leq k$ is NP-complete. Structural as well as algorithmic aspects of this problem have been well studied. We obtain the following results for $\chi_{ON}(G)$:

• Bodlaender, Kolay and Pieterse [WADS 2019] showed the upper bound $\chi_{ON}(G) \leq {\sf fvs}(G) + 3$, where ${\sf fvs}(G)$ denotes the size of a minimum feedback vertex set of $G$. We show the improved bound of $\chi_{ON}(G) \leq {\sf fvs}(G) + 2$, which is tight, thereby answering an open question in the above paper.
• We study the relation between $\chi_{ON}(G)$ and the pathwidth of the graph $G$, denoted ${\sf pw}(G)$. The above paper from WADS 2019 showed the upper bound $\chi_{ON}(G) \leq 2{\sf tw}(G) + 1$ where ${\sf tw}(G)$ stands for the treewidth of $G$. This implies an upper bound of $\chi_{ON}(G) \leq 2{\sf pw}(G) + 1$. We show an improved bound of $\chi_{ON}(G) \leq \lfloor{\frac{5}{3}({\sf pw}(G) + 1)}\rfloor$.
• We prove new bounds for $\chi_{ON}(G)$ with respect to the structural parameters neighborhood diversity and distance to cluster, improving the existing results of Gargano and Rescigno [Theor. Comput. Sci. 2015] and Reddy [Theor. Comput. Sci. 2018], respectively. Furthermore, our techniques also yield improved bounds for the closed neighborhood variant of the problem.
• We prove bounds for $S_k$-free graphs where $S_k$ is a star on $k+1$ vertices. For a graph $G$ with maximum degree $\Delta$, it is known that $\chi_{ON}(G) \leq \Delta + 1$ and this bound is tight in general. When $G$ is $S_k$-free, we show that $\chi_{ON}(G) = O(k \cdot \log^{2 + \epsilon} \Delta)$, for any $\epsilon > 0$. In particular, when G is claw-free, this implies that $\chi_{ON}(G) = O(\log^{2 + \epsilon} \Delta)$. Further, we show existence of claw-free graphs that require $\Omega(\log \Delta)$ colors.
• We also study the partial coloring variant of the CFON coloring problem, which allows vertices to be left uncolored. Let $\chi^*_{ON}(G)$ denote the minimum number of colors required to color $G$ as per this variant. Abel et. al. [SIDMA 2018] showed that $\chi^*_{ON}(G) \leq 8$ when $G$ is planar. They asked if fewer colors would suffice for planar graphs. We answer this question by showing that $\chi^*_{ON}(G) \leq 5$ for all planar $G$. This approach also yields the bound $\chi^*_{ON}(G) \leq 4$ for all outerplanar $G$.

All our bounds are a result of constructive algorithmic procedures.