Choosability on H-free graphs

Petr A. Golovach, Pinar Heggernes, Pim van 't Hof and Daniël Paulusma

Information Processing Letters, vol. 113, no. 4, pp. 107-110, 2013.


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}. We also show that if H is a linear forest, then the problem is fixed-parameter tractable when parameterized by k.