Complexity issues on bounded restrictive H-coloring

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

doi:10.1016/j.disc.2005.12.058

Complexity issues on bounded restrictive H-coloring

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

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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 language	English (US)
Pages (from-to)	2082-2093
Number of pages	12
Journal	Discrete Mathematics
Volume	307
Issue number	16
DOIs	https://doi.org/10.1016/j.disc.2005.12.058
State	Published - Jul 28 2007

Keywords

#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

Access to Document

10.1016/j.disc.2005.12.058

Cite this

@article{6afabde7391e4be8a3673b13d57b9bc7,

title = "Complexity issues on bounded restrictive H-coloring",

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

keywords = "#P-complete, Counting problems, NP-complete, Parameterization, Restrictive H-coloring, Restrictive list H-coloring",

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

year = "2007",

month = jul,

day = "28",

doi = "10.1016/j.disc.2005.12.058",

language = "English (US)",

volume = "307",

pages = "2082--2093",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "16",

}

TY - JOUR

T1 - Complexity issues on bounded restrictive H-coloring

AU - Díaz, Josep

AU - Serna, Maria

AU - Thilikos, Dimitrios M.

PY - 2007/7/28

Y1 - 2007/7/28

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

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

KW - #P-complete

KW - Counting problems

KW - NP-complete

KW - Parameterization

KW - Restrictive H-coloring

KW - Restrictive list H-coloring

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

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

U2 - 10.1016/j.disc.2005.12.058

DO - 10.1016/j.disc.2005.12.058

M3 - Article

AN - SCOPUS:34249293720

SN - 0012-365X

VL - 307

SP - 2082

EP - 2093

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 16

ER -

Complexity issues on bounded restrictive H-coloring

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this