A short note on 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 showed that ${\chi }_{CN}(G)=O({\log }^{2+\epsilon }\mathrm{\Delta })$, for any $\epsilon >0$, where $\mathrm{\Delta }$ is the maximum degree. In 2014, Glebov et al. showed existence of graphs $G$ with ${\chi }_{CN}(G)=\mathrm{\Omega }({\log }^2\mathrm{\Delta })$. In this article, we bridge the gap between the two bounds by showing that ${\chi }_{CN}(G)=O({\log }^2\mathrm{\Delta })$.