Le théorème fort des graphes parfaits
Séminaire Bourbaki : volume 2005/2006, exposés 952-966, Astérisque, no. 311 (2007), Exposé no. 957, pp. 123-135.

Au début des années 60, Claude Berge a proposé deux conjectures sur les graphes parfaits. La première a été démontrée par Laci Lovász en 1972. La deuxième, dite conjecture forte des graphes parfaits, a fait couler beaucoup d'encre dans les 30 années qui ont suivi. Ce n'est qu'en 2002 qu'elle a été démontrée dans un article très impressionnant de 179 pages par Maria Chudnovsky, Neil Robertson, Paul Seymour et Robin Thomas. L'exposé présentera cette conjecture célèbre et donnera une idée de sa démonstration.

In the early 1960s, Claude Berge proposed two conjectures on perfect graphs. The first was proved by Laci Lovasz in 1972. The second generated a lot of activity during the subsequent 30 years. It was proved in 2002 by Maria Chudnovsky, Neil Robertson, Paul Seymour and Robin Thomas in a very impressive 179-page paper that should appear soon in the Annals of Mathematics. This seminar introduces this famous conjecture and gives an idea of its proof.

Classification : 05C17
Mot clés : graphe parfait, Berge, conjecture forte
Keywords: Perfect graph, Berge, strong perfect graph conjecture 
@incollection{SB_2005-2006__48__123_0,
     author = {Cornu\'ejols, G\'erard},
     title = {Le th\'eor\`eme fort des graphes parfaits},
     booktitle = {S\'eminaire Bourbaki : volume 2005/2006, expos\'es 952-966},
     series = {Ast\'erisque},
     note = {talk:957},
     pages = {123--135},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {311},
     year = {2007},
     mrnumber = {2359042},
     zbl = {1194.05047},
     language = {fr},
     url = {http://archive.numdam.org/item/SB_2005-2006__48__123_0/}
}
TY  - CHAP
AU  - Cornuéjols, Gérard
TI  - Le théorème fort des graphes parfaits
BT  - Séminaire Bourbaki : volume 2005/2006, exposés 952-966
AU  - Collectif
T3  - Astérisque
N1  - talk:957
PY  - 2007
SP  - 123
EP  - 135
IS  - 311
PB  - Société mathématique de France
UR  - http://archive.numdam.org/item/SB_2005-2006__48__123_0/
LA  - fr
ID  - SB_2005-2006__48__123_0
ER  - 
%0 Book Section
%A Cornuéjols, Gérard
%T Le théorème fort des graphes parfaits
%B Séminaire Bourbaki : volume 2005/2006, exposés 952-966
%A Collectif
%S Astérisque
%Z talk:957
%D 2007
%P 123-135
%N 311
%I Société mathématique de France
%U http://archive.numdam.org/item/SB_2005-2006__48__123_0/
%G fr
%F SB_2005-2006__48__123_0
Cornuéjols, Gérard. Le théorème fort des graphes parfaits, dans Séminaire Bourbaki : volume 2005/2006, exposés 952-966, Astérisque, no. 311 (2007), Exposé no. 957, pp. 123-135. http://archive.numdam.org/item/SB_2005-2006__48__123_0/

[1] C. Berge - “Färbung von Graphen deren sämtliche bzw. deren ungerade Kreise starr sind (Zusammenfassung)”, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe 10 (1961), p. 114-115.

[2] M. Burlet & J. Fonlupt - “Polynomial algorithm to recognize a Meyniel graph”, Ann. Discrete Math. 21 (1984), p. 225-252. | MR | Zbl

[3] M. Chudnovsky, G. Cornuéjols, X. Liu, P. Seymour & K. Vušković - “Recognizing Berge graphs”, Combinatorica 25 (2005), no. 2, p. 143-186. | MR | Zbl

[4] M. Chudnovsky, N. Robertson, P. Seymour & R. Thomas - “Workshop on Graph Colouring and Decomposition”, exposé oral, Princeton, septembre 2001.

[5] -, “The strong perfect graph theorem”, Ann. of Math. (2) 164 (2006), no. 1, p. 51-229. | MR | Zbl

[6] M. Chudnovsky & P. Seymour - communication personnelle, janvier 2002.

[7] -, communication personnelle, mai 2002.

[8] V. Chvátal - “Star-cutsets and perfect graphs”, J. Combin. Theory Ser. B 39 (1985), no. 3, p. 189-199. | MR | Zbl

[9] V. Chvátal, J. Fonlupt, L. Sun & A. Zemirline - “Recognizing dart-free perfect graphs”, SIAM J. Comput. 31 (2002), no. 5, p. 1315-1338. | MR | Zbl

[10] V. Chvátal & N. Sbihi - “Recognizing claw-free perfect graphs”, J. Combin. Theory Ser. B 44 (1988), no. 2, p. 154-176. | MR | Zbl

[11] -, “Bull-free Berge graphs are perfect”, Graphs Combin. 3 (1987), no. 2, p. 127-139. | MR | Zbl

[12] M. Conforti & G. Cornuéjols - “Graphs without odd holes, parachutes or proper wheels : a generalization of Meyniel graphs and of line graphs of bipartite graphs”, J. Combin. Theory Ser. B 87 (2003), no. 2, p. 300-330. | MR | Zbl

[13] M. Conforti, G. Cornuéjols & K. Vušković - “Decomposition of odd-hole-free graphs by double star cutsets and 2-joins”, Discrete Appl. Math. 141 (2004), no. 1-3, p. 41-91. | MR | Zbl

[14] -, “Square-free perfect graphs”, J. Combin. Theory Ser. B 90 (2004), no. 2, p. 257-307. | MR | Zbl

[15] M. Conforti, G. Cornuéjols & G. Zambelli - “Decomposing Berge graphs containing no proper wheel, subdivided prism or their complements”, Combinatorica 26 (2006), p. 533-558. | DOI | MR | Zbl

[16] G. Cornuéjols & W. H. Cunningham - “Compositions for perfect graphs”, Discrete Math. 55 (1985), no. 3, p. 245-254. | MR | Zbl

[17] J. Fonlupt & A. Zemirline - “A polynomial recognition algorithm for perfect K 4 -{e}-free graphs”, 1986, rapport technique RT-16, Artemis, IMAG, Grenoble, France.

[18] D. R. Fulkerson - “On the perfect graph theorem”, in Mathematical progamming (Madison 1972), Math. Res. Center Publ., vol. 30, Academic Press, New York, 1973, p. 69-76. | MR | Zbl

[19] G. S. Gasparian - “Minimal imperfect graphs : a simple approach”, Combinatorica 16 (1996), no. 2, p. 209-212. | MR | Zbl

[20] D. König - “Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre”, Math. Ann. 77 (1916), no. 4, p. 453-465. | EuDML | JFM | MR

[21] L. Lovász - “A characterization of perfect graphs”, J. Combinatorial Theory Ser. B 13 (1972), p. 95-98. | DOI | MR | Zbl

[22] -, “Normal hypergraphs and the perfect graph conjecture”, Discrete Math. 2 (1972), no. 3, p. 253-267. | MR | Zbl

[23] F. Maffray & B. A. Reed - “A description of claw-free perfect graphs”, J. Combin. Theory Ser. B 75 (1999), no. 1, p. 134-156. | MR | Zbl

[24] M. W. Padberg - “Perfect zero-one matrices”, Math. Programming 6 (1974), p. 180-196. | DOI | MR | Zbl

[25] F. Roussel & P. Rubio - “About skew partitions in minimal imperfect graphs”, J. Combin. Theory Ser. B 83 (2001), no. 2, p. 171-190. | MR | Zbl