Name
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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.disc.2005.12.058 | Discrete Mathematics |
Keywords | Field | DocType |
np-complete,restrictive list h -coloring,restrictive list h-coloring,restrictive h -coloring,counting problems,np -complete,#p-complete,parameterization,restrictive h-coloring,np complete,np,polynomial time,p complete | Discrete mathematics,Combinatorics,NP-complete,Vertex (geometry),Parametrization,P-complete,Counting problem,Time complexity,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
307 | 16 | Discrete Mathematics |
Citations | PageRank | References |
3 | 0.40 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josep Díaz | 1 | 489 | 204.59 |
| Maria Serna | 2 | 216 | 18.19 |
| Dimitrios M. Thilikos | 3 | 1844 | 124.72 |