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

Let G be a graph of maximum degree 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 ' ₂₅ (G). It is known that in general ' ₂₅ (G) 3 ₂ +1, while there is a family of graphs, e. g. the complete graphs, for which ' ₂₅ (G) (1-o (1) ) ₂. In the present paper we provide the asymptotically tight upper bound ' ₂₅ (G) (1+o (1) ) ₂ 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 n^- for any fixed constant (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.