The Complexity of Restrictive H-Coloring

Abstract

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 #H-coloring 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 #itH-coloring problem. Finally, we prove that both results apply also to the list versions of the above problems.

The work of all the authors was supported by the FET Program of the EU under contract number IST-99-14186 (ALCOM-FT)and by the Spanish CYCIT project TIC-2000-1970-CE.The work of the last author was partially supported by the Ministry of Education and Culture of Spain (Resolucin 31/7/00 -BOE 16/8/00).