On the complexity of recognizing decomposable perfect graphs

Abstract : Chvátal, Lenhart and Sbihi identified six classes of graphs that are perfect if and only if two subgraphs induced by a specific colouring of the vertices are perfect. It is well-known that one of these classes is recognizable in polynomial time. We prove that the recognition of the five other classes is NP-complete.
Type de document :
Rapport
[Intern report] A00-R-084 || bazgan00a, 2000, 13 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00099295
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:52:33
Dernière modification le : jeudi 11 janvier 2018 - 06:19:58

Identifiants

  • HAL Id : inria-00099295, version 1

Collections

Citation

Cristina Bazgan, Laurent Juban. On the complexity of recognizing decomposable perfect graphs. [Intern report] A00-R-084 || bazgan00a, 2000, 13 p. 〈inria-00099295〉

Partager

Métriques

Consultations de la notice

157