Pim van 't Hof

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.
[DOI][Preprint]

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