The complexity of restrictive H-coloring

Josep Díaz, Maria Serna, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We define a variant of the H-coloring problem where the number of preimages of certain vertices is predetermined as part of the problem input. We consider the decision and the counting version of the problem; namely the restrictive H-coloring and the restrictive #Hcoloring problems. We provide a dichotomy theorem characterizing the H's for which the restrictive H-coloring problem is either NP-complete or polynomially solvable. Moreover, we prove that the same criterion discriminates the #P-complete and the polynomially solvable cases of the restrictive #H-coloring problem. Finally, we prove that both results apply also to the list versions of the above problems.

Original languageEnglish (US)
Title of host publicationGraph-Theoretic Concepts in Computer Science - 28th International Workshop, WG 2002, Revised Papers
EditorsLudek Kucera
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540003312, 9783540003311
StatePublished - 2002
Event28th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2002 - Cesky Krumlov, Czech Republic
Duration: Jun 13 2002Jun 15 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2573 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference28th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2002
Country/TerritoryCzech Republic
CityCesky Krumlov

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'The complexity of restrictive H-coloring'. Together they form a unique fingerprint.

Cite this