On the complexity of some colorful problems parameterized by treewidth

Michael Fellows, Fedor Fomin, Daniel Lokshtanov, Frances Rosamond, Saket Saurabh, Stefan Szeider, Carsten Thomassen

    Research output: Contribution to journalArticlepeer-review


    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.
    Original languageEnglish
    Pages (from-to)143-153
    Number of pages11
    JournalInformation and Computation
    Issue number2
    Publication statusPublished - 2011


    Dive into the research topics of 'On the complexity of some colorful problems parameterized by treewidth'. Together they form a unique fingerprint.

    Cite this