EnglishDTU.dkIndeksKontaktTelefonbogAlumnenetværkPortalen
Forside > Telefonbog
Titel: On the complexity of some colorful problems parameterized by treewidth
Type: Journal articleJournal article
Person(er):
Forfatter:  Fellows, Michael R.
Technical University of Denmark

Forfatter:  Fomin,, Fedor V.
Technical University of Denmark

Forfatter:  Lokshtanov, Daniel
Technical University of Denmark

Forfatter:  Rosamond, Frances
Technical University of Denmark

Forfatter:  Saurabh, Sakel
Technical University of Denmark

Forfatter:  Szeider, Stefan
Technical University of Denmark

Forfatter:  Thomassen, Carsten (Cwisno: 2460)
Technical University of Denmark
Email:

Uddrag: 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, together with an assignment to each vertex v of a set of colors C"v. The problem is to determine whether it is possible to choose a color for vertex v from the set of permitted colors C"v, 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 vertices where the numbers of vertices having any two distinct colors differs by at most one. We show that the problem is hard for W[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@g"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 L"v of colors, where each list has length at least r, there is a choice of one color from each vertex list L"v yielding a proper coloring of G. We show that the problem of determining whether @g"l(G)=
Publiceret: in journal: Information and Computation (ISSN: 0890-5401) (DOI: http://dx.doi.org/10.1016/j.ic.2010.11.026), vol: 209, issue: 2, pages: 143-153, 2011
DOI:
Fil(er):
Se publikationen i DTU Orbit Se publikationen i DTU Orbit

Top
Matematiktorvet303 B2800 Kgs. LyngbyTlf. 4525 3031CVR-nr. 30 06 09 46EAN-nr. 5798000428515
Cookies