Colouring vertices of trianglefree graphs without forests
Published in:
 Discrete Mathematics.  2012, vol. 312, no. 7, p. 13721385
English
The vertex colouring problem is known to be NPcomplete in the class of trianglefree graphs. Moreover, it is NPcomplete in any subclass of trianglefree graphs defined by a finite collection of forbidden induced subgraphs, each of which contains a cycle. In this paper, we study the vertex colouring problem in subclasses of trianglefree graphs obtained by forbidding graphs without cycles, i.e., forests, and prove polynomialtime solvability of the problem in many classes of this type. In particular, our paper, combined with some previously known results, provides a complete description of the complexity status of the problem in subclasses of trianglefree graphs obtained by forbidding a forest with at most 6 vertices.

Faculty
 Faculté des sciences économiques et sociales

Department
 Département d'informatique

Language


Classification

Computer science

License

License undefined

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/308570
Statistics
Document views: 14
File downloads: