2024/09/01 by Mateusz Kamyczura, Kamyczura, Mateusz, Jakub Przybyło +1
Computer Science · Materials Science · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Nanocluster Synthesis and Applications
paper · pdf · doi:10.48550/arxiv.2409.00759
openalex publication_date 2024/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 χ'\rm CF(G). It is known that in general χ'\rm CF(G)≤ 3 \lceil log2Δ\rceil+1, while there is a family of graphs, e.g. the complete graphs, for which χ'\rm CF(G)≥ (1-o(1))log2Δ. In the present paper we provide the asymptotically tight upper bound χ'\rm CF(G)≤ (1+o(1))log2Δ 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.