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

Bhyravarapu, S. and Kalyanasundaram, S. et al. (2021) Conflict-Free 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)


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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Kalyanasundaram, Subrahmanyam 0000-0001-9094-3368
Item Type: Conference or Workshop Item (Paper)
Additional Information: Series Title: Lecture Notes in Computer Science
Uncontrolled Keywords: Chromatic number; Combined parameter; Conflict-Free Colorings, Decision version, Intersection graph, Proper interval graphs, Undirected graph, Unit disk graphs
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Mrs Haseena VKKM
Date Deposited: 24 Nov 2021 08:40
Last Modified: 02 Mar 2022 09:21
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 9014 Statistics for this ePrint Item