Coloring vertices of claw-free graphs in three colors

We study the computational complexity of the vertex 3-colorability problem in the class of claw-free graphs. Both the problem and the class received much attention in the literature, separately of each other. However, very little is known about the 3-colorability problem restricted to the class of claw-free graphs beyond the fact the problem is NP-complete under this restriction. In this paper we first strengthen this negative fact by revealing various further restrictions under which the problem remains NP-complete. Then we derive a number of positive results that deal with polynomially solvable cases of the problem in the class of claw-free graphs.