2021/12/22 by Bhyravarapu, Sriram, Kalyanasundaram, Subrahmanyam, Mathew, Rogers
#05C15 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2112.12173
The `Conflict-Free Open (Closed) Neighborhood coloring', abbreviated CFON (CFCN) coloring, of a graph G using r colors is a coloring of the vertices of G such that every vertex sees some color exactly once in its open (closed) neighborhood. The minimum r such that G has a CFON (CFCN) coloring using r colors is called the `CFON chromatic number' (`CFCN chromatic number') of G. This is denoted by χCFON(G) (χCFCN(G)). D\k ebski and Przybyło in [J. Graph Theory, 2021] showed that if G is a line graph with maximum degree Δ, then χCFCN(G) = O(ln Δ). As an open question, they asked if the result could be extended to claw-free (K1,3-free) graphs, which are a superclass of line graphs. For k≥ 3, we show that if G is K1,k-free, then χCFON(G) = O(k2ln Δ). Since it is known that the CFCN chromatic number of a graph is at most twice its CFON chromatic number, this answers the question posed by Dębski and Przybyło.