Conflict-Free Coloring of Star-Free Graphs on Open Neighborhoods

2020/09/14 by Sriram Bhyravarapu, Bhyravarapu, Sriram, Subrahmanyam Kalyanasundaram +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2009.06720

openalex publication_date 2020/09/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a graph, the conflict-free coloring problem on open neighborhoods (CFON) asks to color the vertices of the graph so that all the vertices have a uniquely colored vertex in its open neighborhood. The smallest number of colors required for such a coloring is called the conflict-free chromatic number and denoted χ_ON(G). In this note, we study this problem on S_k-free graphs where S_k is a star on k+1 vertices. When G is S_k-free, we show that χ_ON(G) = O(k⋅ log^2+εΔ), for any ε> 0, where Δ denotes the maximum degree of G. Further, we show existence of claw-free (S₃-free) graphs that require Ω(log Δ) colors.

Related

• Conflict-free coloring on open neighborhoods of claw-free graphs
• Extremal Results on Conflict-free Coloring
• Conflict-Free Coloring on Open Neighborhoods
• Bounds and Hardness Results for Conflict-free Choosability
• Combinatorial Bounds for Conflict-free Coloring on Open Neighborhoods