Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover

DOI10.1007/978-3-642-02017-9_25zbMath1241.68071OpenAlexW2175635084MaRDI QIDQ3630207

Jan Kratochvíl, Petr A. Golovach, Jiří Fiala

Publication date: 3 June 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02017-9_25

Mathematics Subject Classification ID

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

Related Items (7)

Kernelization using structural parameters on sparse graph classes ⋮ Distance three labelings of trees ⋮ Parameterizing by the number of numbers ⋮ Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring ⋮ Parameterized complexity of coloring problems: treewidth versus vertex cover ⋮ Data Reduction for Graph Coloring Problems ⋮ Planar Capacitated Dominating Set Is W[1-Hard]

This page was built for publication: Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover