Complexity issues on bounded restrictive H-coloring

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

Research output: Contribution to journalArticlepeer-review


We consider a bounded version of the restrictive and the restrictive list H-coloring problem in which the number of pre-images of certain vertices of H is taken as parameter. We consider the decision and the counting versions, as well as, further variations of those problems. We provide complexity results identifying the cases when the problems are NP-complete or #P-complete or polynomial time solvable. We conclude stating some open problems.

Original languageEnglish (US)
Pages (from-to)2082-2093
Number of pages12
JournalDiscrete Mathematics
Issue number16
StatePublished - Jul 28 2007


  • #P-complete
  • Counting problems
  • NP-complete
  • Parameterization
  • Restrictive H-coloring
  • Restrictive list H-coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Complexity issues on bounded restrictive H-coloring'. Together they form a unique fingerprint.

Cite this