A Conflict-Free Open Neighborhood coloring, abbreviated CFON coloring, of a graph $G = (V, E)$ using $k$ colors is an assignment of colors from a set of $k$ colors to a subset of vertices of $V$ such that every vertex sees some color exactly once in its open neighborhood. The minimum $k$ for which $G$ has a CFON coloring using $k$ colors is called the CFON chromatic number of $G$, denoted by $\chi^*_{ON}(G)$. The analogous notion for closed neighborhood is called CFCN coloring and the analogous parameter is denoted by $\chi^*_{CN}(G)$. The problem of deciding whether a given graph admits a CFON (or CFCN) coloring that uses $k$ colors is NP-complete. Below, we describe briefly the main results of this paper.
We show that it is NP-hard to determine the CFCN chromatic number of chordal graphs. We also show the existence of a family of chordal graphs $G$ that requires $\Omega(\sqrt{\omega(G)})$ colors to CFCN color $G$, where $\omega(G)$ represents the size of a maximum clique in $G$.
We give a polynomial time algorithm to compute $\chi^*_{ON}(G)$ for interval graphs $G$. This answers in positive the open question posed by Reddy [Theoretical Comp. Science, 2018] to determine whether CFON chromatic number can be computed in polynomial time for interval graphs.
We explore biconvex graphs, a subclass of bipartite graphs, and give a polynomial time algorithm to compute their CFON chromatic number.