Conflict-free coloring on subclasses of perfect graphs and bipartite graphs

Abstract

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}^{\ast }(G)$. The analogous notion for closed neighborhood is called CFCN coloring and the analogous parameter is denoted by ${\chi }_{CN}^{\ast }(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 $\mathrm{\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}^{\ast }(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.