Parameterized algorithms for conflict-free colorings of graphs

Show simple item record Reddy, I. Vinod 2018-06-13T12:51:59Z 2018-06-13T12:51:59Z 2018-05
dc.identifier.citation Reddy, I. Vinod, �Parameterized algorithms for conflict-free colorings of graphs�, Theoretical Computer Science, DOI: 10.1016/j.tcs.2018.05.025, May 2018. en_US
dc.identifier.issn 0304-3975
dc.description.abstract In this paper, we study the conflict-free coloring of graphs induced by neighborhoods. A coloring of a graph is conflict-free if every vertex has a uniquely colored vertex in its neighborhood. The conflict-free coloring problem is to color the vertices of a graph using the minimum number of colors such that the coloring is conflict-free. We consider both closed neighborhoods, where the neighborhood of a vertex includes itself, and open neighborhoods, where a vertex does not include in its neighborhood. We study the parameterized complexity of conflict-free closed neighborhood coloring and conflict-free open neighborhood coloring problems. We show that both problems are fixed-parameter tractable (FPT) when parameterized by the cluster vertex deletion number of the input graph. This generalizes the result of Gargano and Rescigno [Theoretical Computer Science, 2015] that conflict-free coloring is FPT parameterized by the vertex cover number. Also, we show that both problems admit an additive constant approximation algorithm when parameterized by the distance to threshold graphs. We also study the complexity of the problem on special graph classes. For split graphs, we give a polynomial time algorithm for closed neighborhood conflict-free coloring problem, whereas we show that open neighborhood conflict-free coloring is NP-complete. For cographs, we show that conflict-free closed neighborhood coloring can be solved in polynomial time and conflict-free open neighborhood coloring need at most three colors. We show that interval graphs can be conflict-free colored using at most four colors.
dc.description.statementofresponsibility by I. Vinod Reddy
dc.language.iso en en_US
dc.publisher Elsevier en_US
dc.subject Conflict-free coloring en_US
dc.subject Parameterized complexity en_US
dc.subject NP-complete en_US
dc.title Parameterized algorithms for conflict-free colorings of graphs en_US
dc.type Article en_US
dc.relation.journal Theoretical Computer Science

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account