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

conflict-free colouring of graphsexponential time hypothesisFPT algorithmsparameterized complexitystrong exponential time hypothesistreewidth

Mathematics Subject Classification ID

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

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

(4)

• Parameterized algorithms for conflict-free colorings of graphs
• Structural parameterization for minimum conflict-free colouring
• Parameterized complexity of conflict-free graph coloring
• Parameterized Complexity of Conflict-Free Graph Coloring

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)