TY - JOUR
AU - Kamiński, Marcin
AU - Lozin, Vadim
PY - 2007/02/07
Y2 - 2022/09/27
TI - Vertex 3-colorability of claw-free graphs
JF - Algorithmic Operations Research
JA - AOR
VL - 2
IS - 1
SE - Articles
DO -
UR - https://journals.lib.unb.ca/index.php/AOR/article/view/2730
SP -
AB - 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
ER -