Parameterized Complexity of Conflict-Free Graph Coloring

DOI10.1137/19M1307160OpenAlexW3198086290MaRDI QIDQ4959657FDOQ4959657

Authors: Sudeshna Kolay, Astrid Pieterse, Hans L. Bodlaender 

Publication date: 17 September 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/19m1307160

Recommendations

• Parameterized complexity of conflict-free graph coloring
• Parameterized algorithms for conflict-free colorings of graphs
• Structural parameterization for minimum conflict-free colouring
• Complexity of conflict-free colorings of graphs
• Minimum conflict free colouring parameterized by treewidth

zbMATH Keywords

fixed-parameter tractabilitykernelizationconflict-free coloringcombinatorial bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Exact exponential algorithms.
• The complexity of satisfiability problems
• Parameterized algorithms
• Kernelization Lower Bounds by Cross-Composition
• Kernel bounds for disjoint cycles and disjoint paths
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Data reduction for graph coloring problems
• Conflict-free colourings of graphs and hypergraphs
• Conflict-free coloring of graphs
• Complexity of conflict-free colorings of graphs
• Conflict-free coloring and its applications
• Conflict-free colouring of graphs
• Conflict-free coloring of points and simple regions in the plane
• Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors
• Optimal sparsification for some binary CSPs using low-degree polynomials
• Known algorithms on graphs of bounded treewidth are probably optimal
• Optimal data reduction for graph coloring using low-degree polynomials
• On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}

Cited In (8)

• Parameterized complexity of conflict-free matchings and paths
• Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs
• Parameterized complexity of the list coloring reconfiguration problem with graph parameters
• Colouring a dominating set without conflicts: \(q\)-subset square colouring
• On odd colorings of planar graphs
• Minimum conflict free colouring parameterized by treewidth
• Conflict-free coloring bounds on open neighborhoods
• Structural parameterization for minimum conflict-free colouring

This page was built for publication: Parameterized Complexity of Conflict-Free Graph Coloring

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