Parameterized algorithms for conflict-free colorings of graphs

DOI10.1016/J.TCS.2018.05.025zbMATH Open1401.68126arXiv1710.00223OpenAlexW2963708823WikidataQ129757968 ScholiaQ129757968MaRDI QIDQ1786593FDOQ1786593

Authors: I. Vinod Reddy 

Publication date: 24 September 2018

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

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.

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

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

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)

Cites Work

• Fundamentals of parameterized complexity
• Complement reducible graphs
• 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
• Parameterized algorithms
• Transitiv orientierbare Graphen
• Parameterized and Exact Computation
• Cluster vertex deletion: a parameterization between vertex cover and clique-width
• Parameterized complexity of vertex colouring
• Graph theory
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• A survey of the algorithmic aspects of modular decomposition
• Deterministic conflict-free coloring for intervals: from offline to online
• Complexity of conflict-free colorings of graphs
• Conflict-free coloring of unit disks
• Exact and FPT algorithms for MAX-conflict free coloring in hypergraphs

Cited In (14)

• 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
• Conflict-free coloring bounds on open neighborhoods
• Structural parameterization for minimum conflict-free colouring

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)