Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

On the complexity of some colourful problems parameterized by treewidth

Fellows, Michael R., Fomin, Fedor, Lokshtanov, Daniel, Rosamond, Frances A., Saurabh, Saket, Szeider, Stefan and Thomassen, Carsten (2011). On the complexity of some colourful problems parameterized by treewidth. Information and Computation,209(2):143-153.

Document type: Journal Article

IRMA ID CDU0002xPUB18
Title On the complexity of some colourful problems parameterized by treewidth
Author Fellows, Michael R.
Fomin, Fedor
Lokshtanov, Daniel
Rosamond, Frances A.
Saurabh, Saket
Szeider, Stefan
Thomassen, Carsten
Journal Name Information and Computation
Publication Date 2011
Volume Number 209
Issue Number 2
ISSN 0890-5401   (check CDU catalogue  open catalogue search in new window)
Start Page 143
End Page 153
Total Pages 10
Place of Publication United States
HERDC Category C1 - Journal Article (DIISR)
Abstract In this paper,we study the complexity of several coloring problems on graphs, parameterized
by the treewidth of the graph.

1. The List Coloring problem takes as input a graph G, togetherwith an assignment to each vertex v of a set of colors Cv. The problem is to determinewhether it is possible to choose a color for vertex v from the set of permitted colors Cv, for each vertex, so that the obtained coloring of G is proper. We show that this problem is W[1]-hard, parameterized by the treewidth of G. The closely related Precoloring Extension problem is also shown to be W[1]-hard, parameterized by treewidth.

2. An equitable coloring of a graph G is a proper coloring of the verticeswhere the numbers of vertices having any two distinct colors differs by at most one.We show that the problem is hard forW[1], parameterized by the treewidth plus the number of colors.We also show that a list-based variation, List Equitable Coloring is W[1]-hard for forests, parameterized
by the number of colors on the lists.

3. The list chromatic number χl(G) of a graph G is defined to be the smallest positive integer r, such that for every assignment to the vertices v of G, of a list Lv of colors, where each list has length at least r, there is a choice of one color fromeach vertex list Lv yielding a proper coloring of G. We show that the problem of determining whether χl(G) ≤ r, the List
Chromatic Number problem, is solvable in linear time on graphs of constant treewidth.
 
Versions
Version Filter Type
Access Statistics: 32 Abstract Views, 9 File Downloads  -  Detailed Statistics
Created: Fri, 17 Jan 2014, 00:58:59 CST