@article{Kamiński_Lozin_2007, title={Vertex 3-colorability of claw-free graphs}, volume={2}, url={https://journals.lib.unb.ca/index.php/AOR/article/view/2730}, abstractNote={The 3-COLORABILITY problem is NP-complete in the class of claw-free graphs. In this paper we study the computational complexity of the problem in subclasses of claw-free graphs deﬁned by forbidding ﬁnitely many additional subgraphs (line graphs and claw-free graphs of bounded vertex degree being examples of such classes). We prove a necessary condition for the polynomial-time solvability of the problem in such classes and propose a linear-time solution for an inﬁnitely increasing hierarchy of classes that meet the condition. To develop such a solution for the basis of this hierarchy, we generalize the notion of locally connected graphs that has been recently studied in the context of the 3-COLORABILITY problem. Key words: Vertex 3-colorability; Claw-free graphs; Polynomial-time algorithm}, number={1}, journal={Algorithmic Operations Research}, author={Kamiński, Marcin and Lozin, Vadim}, year={2007}, month={Feb.} }