On asymptotically tight bound for the conflict-free chromatic index of nearly regular graphs

Abstract

Let $G$ be a graph of maximum degree $\Delta$ which does not contain isolated vertices. An edge coloring $c$ of $G$ is called conflict-free if each edge's closed neighborhood includes a uniquely colored element. The least number of colors admitting such $c$ is called the conflict-free chromatic index of $G$ and denoted ${\chi }_{\mathrm{CF}}^{\prime }(G)$. It is known that in general ${\chi }_{\mathrm{CF}}^{\prime }(G)\le 3\lceil {\log }_2\Delta \rceil +1$, while there is a family of graphs, e.g. the complete graphs, for which ${\chi }_{\mathrm{CF}}^{\prime }(G)\ge (1-o(1)){\log }_2\Delta$. In the present paper we provide the asymptotically tight upper bound ${\chi }_{\mathrm{CF}}^{\prime }(G)\le (1+o(1)){\log }_2\Delta$ for regular and nearly regular graphs, which in particular implies that the same bound holds a.a.s. for a random graph $G=G(n,p)$ whenever $p\gg n^{-\epsilon }$ for any fixed constant $\epsilon \in (0,1)$. Our proof is probabilistic and exploits classic results of Hall and Berge. This was inspired by our approach utilized in the particular case of complete graphs, for which we give a more specific upper bound. We also observe that almost the same bounds hold in the open neighborhood regime.

14 pages