Conflict-Free Coloring on Claw-Free Graphs and Interval 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(G)$ 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.

• For $k \geq 3$, we show that if $G$ is a $K_{1,k}$-free graph then $\chi_{ON}^*(G) = O(k^2\log \Delta)$, where $\Delta$ denotes the maximum degree of $G$. Dębski and Przybyło in [J. Graph Theory, 2021] had shown that if $G$ is a line graph, then $\chi_{CN}^*(G) = O(\log \Delta)$. As an open question, they had asked if their result could be extended to claw-free ($K_{1,3}$-free) graphs, which are a superclass of line graphs. Since it is known that the CFCN* chromatic number of a graph is at most twice its CFON* chromatic number, our result positively answers the open question posed by Dębski and Przybyło.
• We show that if the minimum degree of any vertex in $G$ is $\Omega(\Delta/(\log^{\epsilon} \Delta))$ for some $\epsilon \geq 0$, then $\chi_{ON}^*(G) = O(\log^{1+\epsilon}\Delta)$. This is a generalization of the result given by Dębski and Przybyło in the same paper where they showed that if the minimum degree of any vertex in $G$ is $\Omega (\Delta)$, then $\chi_{ON}^*(G)= O(\log \Delta)$.
• 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 the CFON* chromatic number can be computed in polynomial time on interval graphs.
• We explore biconvex graphs, a subclass of bipartite graphs and give a polynomial time algorithm to compute their CFON* chromatic number. This is interesting as Abel et al. [SIDMA, 2018] had shown that it is NP-complete to decide whether a planar bipartite graph $G$ has $\chi_{ON}^*(G) = k$ where $k \in {1, 2, 3 }$.