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

Abstract

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\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.