Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover

摘要

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.