Parameterized complexity of coloring problems: treewidth versus vertex cover (extended abstract). (English) Zbl 1241.68071

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

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].

MSC:

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