The Strong Perfect Graph Conjecture: 40 years of Attempts, and its Resolution

Abstract : The Strong Perfect Graph Conjecture (SPGC) was certainly one of the most challenging conjectures in graph theory. During more than four decades, numerous attempts were made to solve it, by combinatorial methods, by linear algebraic methods, or by polyhedral methods. The first of these three approaches yielded the first (and to date only) proof of the SPGC; the other two remain promising to consider in attempting an alternative proof. This paper is an unbalanced survey of the attempts to solve the SPGC; unbalanced, because (1) we devote a signicant part of it to the 'primitive graphs and structural faults' paradigm which led to the Strong Perfect Graph Theorem (SPGT); (2) we briefly present the other "direct" attempts, that is, the ones for which results exist showing one (possible) way to the proof; (3) we ignore entirely the "indirect" approaches whose aim was to get more information about the properties and structure of perfect graphs, without a direct impact on the SPGC. Our aim in this paper is to trace the path that led to the proof of the SPGT as completely as possible. Of course, this implies large overlaps with the recent book on perfect graphs [J.L. Ramirez-Alfonsin and B.A. Reed, eds., Perfect Graphs (Wiley & Sons, 2001).], but it also implies a deeper analysis (with additional results) and another viewpoint on the topic.
Keywords : perfect graph coloring
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2009, 309 (20), pp.6092-6113
Liste complète des métadonnées

Littérature citée [98 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00475637
Contributeur : Irena Rusu <>
Soumis le : vendredi 23 avril 2010 - 09:41:53
Dernière modification le : jeudi 5 avril 2018 - 10:36:49
Document(s) archivé(s) le : mardi 28 septembre 2010 - 12:38:14

Fichier

SPGT-40-years.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00475637, version 1

Citation

Florian Roussel, Irena Rusu, Henri Thuillier. The Strong Perfect Graph Conjecture: 40 years of Attempts, and its Resolution. Discrete Mathematics, Elsevier, 2009, 309 (20), pp.6092-6113. 〈inria-00475637〉

Partager

Métriques

Consultations de la notice

230

Téléchargements de fichiers

329