All Questions
Tagged with parameterized-complexity graph-colouring
2 questions
3
votes
0
answers
319
views
Difficulty of graph coloring and independent set?
Given a graph on $n$ vertices it is strongly $NP$-complete to decide it is $3$-colorable while it is easy to decide it is $n$-colorable.
Is there a parsimonious reduction from SUBSET-SUM to GRAPH-3-...
- 549
7
votes
3
answers
773
views
Hard problems for bounded vertex cover
We know that list coloring problem is W[1]-hard when parameterized by vertex cover. Are there any other problems which are also W[1]-hard parameterized by vertex cover?
- 2,044