Conflict-free coloring on closed neighborhoods of bounded degree graphs

Abstract

The closed neighborhood conflict-free chromatic number of a graph $G$, denoted by ${\chi }_{CN}(G)$, is the minimum number of colors required to color the vertices of $G$ such that for every vertex, there is a color that appears exactly once in its closed neighborhood. Pach and Tardos [Combin. Probab. Comput. 2009] showed that ${\chi }_{CN}(G)=O({\log }^{2+\epsilon }\Delta )$, for any $\epsilon >0$, where $\Delta$ is the maximum degree. In [Combin. Probab. Comput. 2014], Glebov, Szabó and Tardos showed existence of graphs $G$ with ${\chi }_{CN}(G)=\Omega ({\log }^2\Delta )$. In this paper, we bridge the gap between the two bounds by showing that ${\chi }_{CN}(G)=O({\log }^2\Delta )$.

4 pages