Choosability on H-free graphs

0.00 Avg rating—0 Votes

Article ID:	iaor2013783
Volume:	113
Issue:	4
Start Page Number:	107
End Page Number:	110
Publication Date:	Feb 2013
Journal:	Information Processing Letters
Authors:	Paulusma Danil, Heggernes Pinar, van 't Hof Pim, Golovach Petr A
Keywords:	graphs, sets

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

Reviews

Required fields are marked *. Your email address will not be published.