Given an undirected graph, a conflict-free coloring (CFON*) is an assignment of colors to a subset of the vertices of the graph such that for every vertex there exists a color that is assigned to exactly one vertex in its open neighborhood. The minimum number of colors required for such a coloring is called the conflict-free chromatic number. The decision version of the CFON* problem is NP-complete even on planar graphs. In this paper, we show the following results.

- The CFON* problem is fixed parameter tractable with respect to the combined parameters clique width and the solution size.

- We study the problem on block graphs and cographs, which have bounded clique width. For both graph classes, we give tight bounds of three and two respectively for the CFON* chromatic number.

- We study the problem on the following intersection graphs: interval graphs, unit square graphs and unit disk graphs. We give tight bounds of two and three for the CFON* chromatic number for proper interval graphs and interval graphs. Moreover, we give upper bounds for the CFON* chromatic number on unit square and unit disk graphs.

- We also study the problem on split graphs and Kneser graphs. For split graphs, we show that the problem is NP-complete. For Kneser graphs K(n,k), when n\geq k(k+1)^2 + 1, we show that the CFON* chromatic number is k+1.

We also study the closed neighborhood variant of the problem denoted by CFCN*, and obtain analogous results in some of the above cases.

https://link.springer.com/chapter/10.1007/978-3-030-79987-8_7