A coloring algorithm for 4K1-free line graphs

Given a family F of graphs, let Free (F) be the class of graphs that do not contain any member of F as an induced subgraph. When F is a set of four-vertex graphs the complexity of the vertex coloring problem in Free (F) is known, with three exceptions: F={claw,4K1}, F={claw,4K1,co-diamond}, and F={C4,4K1}. In this paper, we study the coloring problem for Free (claw, 4K1). We solve the vertex coloring problem for a subclass of Free (claw, 4K1) which contains the class of 4K1-free line graphs.