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

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 ${\chi }_{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 ${\chi }_{ON}(G)=O(k\cdot {\log }^{2+\epsilon }\Delta )$, for any $\epsilon >0$, where $\Delta$ denotes the maximum degree of $G$. Further, we show existence of claw-free ($S_3$-free) graphs that require $\Omega (\log \Delta )$ colors.

References in corpus (1)

• Conflict-free chromatic number vs conflict-free chromatic index