Bhyravarapu, S. and Kalyanasundaram, S. et al.
(2021)
ConflictFree Coloring: Graphs of Bounded Clique Width and Intersection Graphs.
In: 32nd International Workshop on Combinatorial Algorithms, IWOCA 2021, 5 July 2021 through 7 July 2021, Virtual, Online.
Full text not available from this repository.
(
Request a copy)
Abstract
Given an undirected graph, a conflictfree 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 conflictfree chromatic number. The decision version of the CFON* problem is NPcomplete even on planar graphs. In this paper, we show the following results. The CFON* problem is fixedparameter 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 NPcomplete. 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.
[error in script]
Actions (login required)

View Item 