Conflict-Free Coloring: Graphs of Bounded Clique Width and Intersection Graphs

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 or 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 >= 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.