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 journalArticle

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

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

  • Cite this

    Fellows, M., Fomin, F., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., & Thomassen, C. (2011). On the complexity of some colorful problems parameterized by treewidth. Information and Computation, 209(2), 143-153. https://doi.org/10.1016/j.ic.2010.11.026