Minimum conflict free colouring parameterized by treewidth

DOI10.1007/978-3-030-39219-2_35MaRDI QIDQ779250zbMATH OpenOpenAlexFDO

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

Publication date 21 July 2020

Full work available at URL https://doi.org/10.1007/978-3-030-39219-2_35

zbMATH Keywords

treewidthexponential time hypothesisparameterized complexityFPT algorithmsconflict-free colouring of graphsstrong exponential time hypothesis

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Structural parameterization for minimum conflict-free colouring
• Parameterized complexity of conflict-free graph coloring
• Parameterized Complexity of Conflict-Free Graph Coloring
• Parameterized algorithms for conflict-free colorings of graphs
• Tree-coloring problems of bounded treewidth graphs
• Complexity of conflict-free colorings of graphs
• Conflict-free colouring of graphs
• Conflict-free coloring: graphs of bounded clique width and intersection graphs
• On the Complexity of Some Colorful Problems Parameterized by Treewidth
• On the complexity of some colorful problems parameterized by treewidth

Cited in

(2)

• Structural parameterization for minimum conflict-free colouring
• Parameterized algorithms for conflict-free colorings of graphs

This page was built for publication: Minimum conflict free colouring parameterized by treewidth

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