Extremal Results on Conflict-free Coloring

A conflict-free open neighborhood coloring of a graph is an assignment of colors to the vertices such that for every vertex there is a color that appears exactly once in its open neighborhood. For a graph G, the smallest number of colors required for such a coloring is called the conflict-free open neighborhood (CFON) chromatic number and is denoted by \chi_{ON}(G). Analogously, we define conflict-free closed neighborhood (CFCN) coloring, and CFCN chromatic number (denoted by \chi_{CN}(G)). First studied in 2002, this problem has received considerable attention. We study the CFON and CFCN coloring problems and show the following results. In what follows, \Delta denotes the maximum degree of the graph. 1. For a K_{1, k}-free graph G, we show that \chi_{ON}(G) = O(k \ln\Delta). This improves the bound of O(k^2 \ln \Delta) from [Bhyravarapu, Kalyanasundaram, Mathew, MFCS 2022]. Since \chi_{CN}(G) \leq 2\chi_{ON}(G), our result implies an upper bound on \chi_{CN}(G) as well. It is known that there exist separate classes of graphs with \chi_{ON}(G) = \Omega(\ln\Delta) and \chi_{ON}(G) = \Omega(k). 2. Let f(\delta) be defined as follows: f(\delta) = max {\chi_{CN} (G) : G is a graph with minimum degree \delta}. It is easy to see that f(\delta') \geq f(\delta) when \delta' < \delta. It is known [Debski and Przybylo, JGT 2021] that f(c \Delta) = \Theta(\log \Delta), for any positive constant c. In this paper, we show that f(c\Delta^{1 - \epsilon}) = \Omega (\ln^2 \Delta), where c, \epsilon are positive constants such that \epsilon < 0.75. Together with the known upper bound \chi_{CN}(G) = O(\ln^2 \Delta), this implies that f(c\Delta^{1 - \epsilon}) = \Theta (\ln^2 \Delta). 3. For a K_{1, k}-free graph G on n vertices, we show that \chi_{CN}(G) = O(\ln k \ln n). This bound is asymptotically tight.