The complexity of restrictive H-coloring

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

doi:10.1007/3-540-36379-3_12

The complexity of restrictive H-coloring

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 #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 language	English (US)
Title of host publication	Graph-Theoretic Concepts in Computer Science - 28th International Workshop, WG 2002, Revised Papers
Editors	Ludek Kucera
Publisher	Springer Verlag
Pages	126-137
Number of pages	12
ISBN (Print)	3540003312, 9783540003311
DOIs	https://doi.org/10.1007/3-540-36379-3_12
State	Published - 2002
Event	28th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2002 - Cesky Krumlov, Czech Republic Duration: Jun 13 2002 → Jun 15 2002

Publication series

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

Conference

Conference	28th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2002
Country/Territory	Czech Republic
City	Cesky Krumlov
Period	6/13/02 → 6/15/02

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-36379-3_12

Cite this

Díaz, J., Serna, M., & Thilikos, D. M. (2002). The complexity of restrictive H-coloring. In L. Kucera (Ed.), Graph-Theoretic Concepts in Computer Science - 28th International Workshop, WG 2002, Revised Papers (pp. 126-137). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2573 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-36379-3_12

The complexity of restrictive H-coloring. / Díaz, Josep; Serna, Maria; Thilikos, Dimitrios M.
Graph-Theoretic Concepts in Computer Science - 28th International Workshop, WG 2002, Revised Papers. ed. / Ludek Kucera. Springer Verlag, 2002. p. 126-137 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2573 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Díaz, J, Serna, M & Thilikos, DM 2002, The complexity of restrictive H-coloring. in L Kucera (ed.), Graph-Theoretic Concepts in Computer Science - 28th International Workshop, WG 2002, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2573 LNCS, Springer Verlag, pp. 126-137, 28th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2002, Cesky Krumlov, Czech Republic, 6/13/02. https://doi.org/10.1007/3-540-36379-3_12

Díaz J, Serna M, Thilikos DM. The complexity of restrictive H-coloring. In Kucera L, editor, Graph-Theoretic Concepts in Computer Science - 28th International Workshop, WG 2002, Revised Papers. Springer Verlag. 2002. p. 126-137. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-36379-3_12

Díaz, Josep ; Serna, Maria ; Thilikos, Dimitrios M. / The complexity of restrictive H-coloring. Graph-Theoretic Concepts in Computer Science - 28th International Workshop, WG 2002, Revised Papers. editor / Ludek Kucera. Springer Verlag, 2002. pp. 126-137 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c5f23544f4a84288867aef2484c3e79b,

title = "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 #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.",

author = "Josep D{\'i}az and Maria Serna and Thilikos, {Dimitrios M.}",

year = "2002",

doi = "10.1007/3-540-36379-3_12",

language = "English (US)",

isbn = "3540003312",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "126--137",

editor = "Ludek Kucera",

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

note = "28th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2002 ; Conference date: 13-06-2002 Through 15-06-2002",

}

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 -

The complexity of restrictive H-coloring

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this