Conflict-free coloring on open neighborhoods of claw-free graphs

12/22/2021
by   Sriram Bhyravarapu, et al.
0

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 χ_CF^ON(G) (χ_CF^CN(G)). Dębski and Przybyło in [J. Graph Theory, 2021] showed that if G is a line graph with maximum degree Δ, then χ_CF^CN(G) = O(lnΔ). As an open question, they asked if the result could be extended to claw-free (K_1,3-free) graphs, which are a superclass of line graphs. For k≥ 3, we show that if G is K_1,k-free, then χ_CF^ON(G) = O(k^2lnΔ). 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset