zbMATH — the first resource for mathematics

Parameterized complexity of coloring problems: treewidth versus vertex cover (extended abstract). (English) Zbl 1241.68071
Chen, Jianer (ed.) et al., Theory and applications of models of computation. 6th annual conference, TAMC 2009, Changsha, China, May 18–22, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02016-2/pbk). Lecture Notes in Computer Science 5532, 221-230 (2009).
Summary: We compare the fixed-parameter complexity of various variants of coloring problems (including List Coloring, Precoloring Extension, Equitable Coloring, \(L(p,1)\)-Labeling and Channel Assignment) when parameterized by treewidth and by vertex cover number. In most (but not all) cases we conclude that parametrization by the vertex cover number provides a significant drop in the complexity of the problems.
For the entire collection see [Zbl 1163.68001].

68Q25 Analysis of algorithms and problem complexity
05C15 Coloring of graphs and hypergraphs
Full Text: DOI