2023/05/04 by Shiwali Gupta, Bhyravarapu, Sriram, Subrahmanyam Kalyanasundaram +4
Computer Science · Mathematics · #05C15 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2305.02570
openalex publication_date 2023/05/04 · openalex created_date 2023/05/07 · openalex updated_date 2026/07/28
A conflict-free open neighborhood coloring of a graph is an assignment of colors to the vertices such that for every vertex there is a color that appears exactly once in its open neighborhood. For a graph G, the smallest number of colors required for such a coloring is called the conflict-free open neighborhood (CFON) chromatic number and is denoted by χON(G). By considering closed neighborhood instead of open neighborhood, we obtain the analogous notions of conflict-free closed neighborhood (CFCN) coloring, and CFCN chromatic number (denoted by χCN(G)). The notion of conflict-free coloring was introduced in 2002, and has since received considerable attention. In this paper, we study some extremal questions related to CFON and CFCN coloring.