TY - GEN

T1 - The complexity of restrictive H-coloring

AU - Díaz, Josep

AU - Serna, Maria

AU - Thilikos, Dimitrios M.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84901442945&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84901442945&partnerID=8YFLogxK

U2 - 10.1007/3-540-36379-3_12

DO - 10.1007/3-540-36379-3_12

M3 - Conference contribution

AN - SCOPUS:84901442945

SN - 3540003312

SN - 9783540003311

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 126

EP - 137

BT - Graph-Theoretic Concepts in Computer Science - 28th International Workshop, WG 2002, Revised Papers

A2 - Kucera, Ludek

PB - Springer Verlag

T2 - 28th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2002

Y2 - 13 June 2002 through 15 June 2002

ER -