Parameterized Complexity of Conflict-Free Graph Coloring
From MaRDI portal
Publication:4959657
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
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)