Extremal Results on Conflict-Free Coloring

Abstract

A conflict-free open neighborhood (CFON) 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 CFON chromatic number and is denoted by $\chi_{ON}(G)$. By considering closed neighborhood instead of open neighborhood, we obtain the analogous notions of conflict-free (CF) closed neighborhood (CFCN) coloring, and CFCN chromatic number (denoted by $\chi_{CN}(G)$). The notion of CF coloring was introduced in 2002, and has since received considerable attention. We study CFON and CFCN colorings and show the following results. In what follows, $\Delta$ denotes the maximum degree of the graph.

• We show that if $G$ is a $K_{1,k}$-free graph, then $\chi_{ON}(G) = O(k \ln \Delta)$. Dębski and Przybyło had shown that if $G$ is a line graph, then $\chi_{CN}(G) = O(\ln \Delta)$. As an open question, they had asked if their result could be extended to claw-free ($K_{1,3}$-free) graphs, which is a superclass of line graphs. Since $\chi_{CN}(G) \leq 2 \chi_{ON}(G)$, our result answers their open question. It is known that there exist separate families of $K_{1,k}$-free graphs with $\chi_{ON}(G) = \Omega(\ln \Delta)$ and $\chi_{ON}(G) = \Omega(k)$.
• For a $K_{1,k}$-free graph on $n$ vertices, we show that $\chi_{CN}(G) = O(\ln k \ln n)$. This bound is asymptotically tight for some values of $k$ since there are graphs $G$ with $\chi_{CN}(G) = \Omega(\ln^2 n)$.
• Let $\delta \geq 0$ be an integer. We define $f_{CN}(\delta)$ as follows: $$f_{CN}(\delta) = \max{\chi_{CN}(G) : G \text{ is a graph with minimum degree at least } \delta }.$$ It is easy to see that $f_{CN}(\delta’) \geq f_{CN}(\delta)$, when $\delta’ < \delta$. Let $c$ be a positive constant. It was shown that $f_{CN}(c \Delta) = \Theta(\ln \Delta)$. In this paper, we show (i) $f_{CN}(\frac{c \Delta}{\ln^{\epsilon}\Delta}) = O(\ln^{1 + \epsilon}\Delta)$, where $\epsilon$ is a constant such that $0 < \epsilon \leq 1$ and (ii) $f_{CN}(c\Delta^{1- \epsilon}) = \Omega(\ln^2 \Delta)$, where $\epsilon$ is a constant such that $0 < \epsilon < 0.003$. Together with the known upper bound $\chi_{CN}(G) = O(\ln^2(\Delta)$, this implies that $f_{CN}(c\Delta^{1- \epsilon}) = \Theta(\ln^2 \Delta)$.