Name
Abstract | ||
|---|---|---|
A graph is H-free if it has no induced subgraph isomorphic to H. We determine the computational complexity of the Choosability problem restricted to H-free graphs for every graph H that does not belong to {K"1","3,P"1+P"2,P"1+P"3,P"4}. We also show that if H is a linear forest, then the problem is fixed-parameter tractable when parameterized by k. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.ipl.2012.12.003 | Inf. Process. Lett. |
Keywords | Field | DocType |
induced subgraph isomorphic,fixed-parameter tractable,choosability problem,h-free graph,linear forest,graph h,computational complexity | Discrete mathematics,Graph,Combinatorics,Parameterized complexity,Induced subgraph,Isomorphism,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
113 | 4 | 0020-0190 |
Citations | PageRank | References |
2 | 0.36 | 19 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Petr A. Golovach | 1 | 766 | 83.25 |
| Pinar Heggernes | 2 | 845 | 72.39 |
| Pim van 't Hof | 3 | 209 | 20.75 |
| Daniël Paulusma | 4 | 712 | 78.49 |