On the complexity of a restricted list-coloring problem

Moshe Dror, Gerd Finke, Sylvain Gravier, Wieslaw Kubiak

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


We investigate a restricted list-coloring problem. Given a graph G = (V,E), a non empty set of colors L, and a nonempty subset L(v) of L for each vertex v, find an L-coloring of G with the size of each class of colors being equal to a given integer. This restricted list-coloring problem was proposed by de Werra. We prove that this problem is script N sign P-Complete even if the graph is a path with at most two colors on each vertex list. We then give a polynomial algorithm which solves this problem for the case where the total number of colors occurring in all lists is fixed.

Original languageEnglish (US)
Pages (from-to)103-109
Number of pages7
JournalDiscrete Mathematics
Issue number1-3
StatePublished - 1999
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On the complexity of a restricted list-coloring problem'. Together they form a unique fingerprint.

Cite this