Complexity of conflict-free colorings of graphs
From MaRDI portal
Publication:484316
DOI10.1016/j.tcs.2014.11.029zbMath1317.68071OpenAlexW2033159765MaRDI QIDQ484316
Adele A. Rescigno, Luisa Gargano
Publication date: 6 January 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.11.029
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (25)
Iterated Type Partitions ⋮ Parameterized complexity of immunization in the threshold model ⋮ Conflict-Free Coloring of Graphs ⋮ Conflict-Free Coloring of Intersection Graphs ⋮ Conflict-free coloring bounds on open neighborhoods ⋮ Structural parameterization for minimum conflict-free colouring ⋮ A tight bound for conflict-free coloring in terms of distance to cluster ⋮ Integer programming in parameterized complexity: five miniatures ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Immunization in the threshold model: a parameterized complexity study ⋮ Colouring a dominating set without conflicts: \(q\)-subset square colouring ⋮ Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU ⋮ Parameterized complexity for iterated type partitions and modular-width ⋮ Spanning trees with few branch vertices in graphs of bounded neighborhood diversity ⋮ Conflict-free coloring of intersection graphs of geometric objects ⋮ A Short Note on Open-Neighborhood Conflict-Free Colorings of Graphs ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs ⋮ Conflict-free coloring of string graphs ⋮ Parameterized algorithms for conflict-free colorings of graphs ⋮ Parameterized Complexity of Conflict-Free Graph Coloring ⋮ Evangelism in Social Networks ⋮ Unnamed Item ⋮ Coloring a dominating set without conflicts: \(q\)-subset square coloring ⋮ Conflict-free coloring: graphs of bounded clique width and intersection graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Conflict-free coloring of points on a line with respect to a set of intervals
- Strong conflict-free coloring for intervals
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Graph unique-maximum and conflict-free colorings
- Improved upper bounds for vertex cover
- Conflict-free coloring of points and simple regions in the plane
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
- Conflict-Free Colourings of Graphs and Hypergraphs
- Clique-Width is NP-Complete
- Algorithmic Meta-theorems for Restrictions of Treewidth
- Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
- Online Conflict-Free Colouring for Hypergraphs
- Conflict-Free Colouring of Graphs
This page was built for publication: Complexity of conflict-free colorings of graphs
