Parameterized algorithms for conflict-free colorings of graphs

DOI10.1016/J.TCS.2018.05.025MaRDI QIDQ1786593zbMATH OpenOpenAlexWikidataFDO

Authors I. Vinod Reddy

Publication date 24 September 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.00223

zbMATH Keywords

NP-completeparameterized complexityconflict-free coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

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 included 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 et al.(2015) that conflict-free coloring is fixed-parameter tractable 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. We show that both problems can be solved in polynomial time on cographs. 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. We show that interval graphs can be conflict-free colored using at most four colors.

Recommendations

• Complexity of conflict-free colorings of graphs
• Conflict-free coloring of graphs
• Minimum conflict free colouring parameterized by treewidth
• A tight bound for conflict-free coloring in terms of distance to cluster
• Remarks on proper conflict-free colorings of graphs

Cites work

• A survey of the algorithmic aspects of modular decomposition
• Cluster vertex deletion: a parameterization between vertex cover and clique-width
• Complement reducible graphs
• Complexity of conflict-free colorings of graphs
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-free coloring of unit disks
• Deterministic conflict-free coloring for intervals: from offline to online
• Exact and FPT algorithms for MAX-conflict free coloring in hypergraphs
• Fundamentals of parameterized complexity
• Graph theory
• Parameterized algorithms
• Parameterized and Exact Computation
• Parameterized complexity of vertex colouring
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Transitiv orientierbare Graphen

Cited in

(14)

• Conflict-free coloring bounds on open neighborhoods
• Structural parameterization for minimum conflict-free colouring
• Parameterized complexity of conflict-free matchings and paths
• Remarks on proper conflict-free colorings of graphs
• Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs
• Backdoor DNFs
• Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
• Conflict-free coloring: graphs of bounded clique-width and intersection graphs
• Parameterized algorithms for load coloring problem
• Parameterized and exact algorithms for class domination coloring
• A tight bound for conflict-free coloring in terms of distance to cluster
• Minimum conflict free colouring parameterized by treewidth
• Complexity of conflict-free colorings of graphs
• Conflict-free coloring: graphs of bounded clique width and intersection graphs

This page was built for publication: Parameterized algorithms for conflict-free colorings of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1786593)