Résumés
Abstract
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 defined by forbidding finitely 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 infinitely 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
Keywords:
- Vertex 3-colorability,
- Claw-free graphs,
- Polynomial-time algorithm
Veuillez télécharger l’article en PDF pour le lire.
Télécharger