Name
Abstract | ||
|---|---|---|
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.
|
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.tcs.2010.10.043 | Theory and Applications of Models of Computation |
Keywords | Field | DocType |
Graph labelings,Graph colorings,vertex cover number,various variant,Channel Assignment,Precoloring Extension,Parameterized complexity,List Coloring,Vertex cover,fixed parameter complexity,Equitable Coloring,coloring problem,significant drop | Discrete mathematics,Complete coloring,Combinatorics,Parameterized complexity,Fractional coloring,List coloring,Vertex cover,Treewidth,Mathematics,Graph coloring,Equitable coloring | Journal |
Volume | Issue | ISSN |
412 | 23 | Theoretical Computer Science |
Citations | PageRank | References |
26 | 1.06 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jiří Fiala | 1 | 300 | 24.05 |
| Petr A. Golovach | 2 | 766 | 83.25 |
| Jan Kratochvíl | 3 | 1751 | 151.84 |