Choosability on H-free graphs

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.