| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427538 | Information Processing Letters | 2013 | 4 Pages |
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 {K1,3,P1+P2,P1+P3,P4}{K1,3,P1+P2,P1+P3,P4}. We also show that if H is a linear forest, then the problem is fixed-parameter tractable when parameterized by k.
► We show that Choosability restricted to H -free graphs is NP-hard if H∉{K1,3,P1,2P1,3P1,P1+P2,P1+P3,P2,P3,P4}H∉{K1,3,P1,2P1,3P1,P1+P2,P1+P3,P2,P3,P4}. ► We show that Choosability restricted to H -free graphs is polynomial-time solvable if H∈{P1,2P1,3P1,P2,P3}H∈{P1,2P1,3P1,P2,P3}. ► We show that if H is a linear forest, then Choosability is fixed-parameter tractable with parameter k for H-free graphs.
