Structural parameterization for minimum conflict-free colouring

DOI10.1016/j.dam.2021.12.026OpenAlexW4210558012WikidataQ114191471 ScholiaQ114191471MaRDI QIDQ2161251

Rathin Bhargava, Pradeesha Ashok, Dolly Yadav, Mohammad Khalid, Naman Gupta

Publication date: 4 August 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2021.12.026

zbMATH Keywords

treewidthvertex coverparameterized complexityexponential time hypothesiskernelizationFPT algorithmsconflict-free colouring of graphsstrong exponential time hypothesis

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Colouring a dominating set without conflicts: \(q\)-subset square colouring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors
• Complexity of conflict-free colorings of graphs
• The weighted perfect domination problem
• Conflict-free coloring of unit disks
• Parameterized complexity of conflict-free graph coloring
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Conflict-Free Colourings of Graphs and Hypergraphs
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
• Conflict-Free Coloring of Graphs
• Kernelization Lower Bounds by Cross-Composition
• The complexity of satisfiability problems
• Parameterized Algorithms