2020/09/04 by Michał Dębski, Dębski, Michał, Jakub Przybyło +1
Computer Science · Mathematics · #05C15 #Advanced Image and Video Retrieval Techniques #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics #math.CO #msc:05C15
paper · pdf · doi:10.48550/arxiv.2009.02239
10 pages
arxiv created 2020/09/04 · openalex publication_date 2020/09/04 · arxiv updated 2020/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A vertex coloring of a given graph G is conflict-free if the closed neighborhood of every vertex contains a unique color (i.e. a color appearing only once in the neighborhood). The minimum number of colors in such a coloring is the conflict-free chromatic number of G, denoted χCF(G). What is the maximum possible conflict-free chromatic number of a graph with a given maximum degree Δ? Trivially, χCF(G)≤ χ(G)≤ Δ+1, but it is far from optimal - due to results of Glebov, Szabó and Tardos, and of Bhyravarapu, Kalyanasundaram and Mathew, the answer in known to be Θ(ln2Δ). We show that the answer to the same question in the class of line graphs is Θ(lnΔ) - that is, the extremal value of the conflict-free chromatic index among graphs with maximum degree Δ is much smaller than the one for conflict-free chromatic number. The same result for χCF(G) is also provided in the class of near regular graphs, i.e. graphs with minimum degree δ≥ αΔ.