Le théorème fort des graphes parfaits  [ The strong perfect graph theorem ]
Séminaire Bourbaki : volume 2005/2006, exposés 952-966, Astérisque no. 311  (2007), Talk no. 957, p. 123-135

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.

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.

Classification:  05C17
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},
     author = {Collectif},
     series = {Ast\'erisque},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {311},
     year = {2007},
     note = {talk:957},
     pages = {123-135},
     zbl = {1194.05047},
     mrnumber = {2359042},
     language = {fr},
     url = {http://www.numdam.org/item/SB_2005-2006__48__123_0}
}
Cornuéjols, Gérard. Le théorème fort des graphes parfaits, in Séminaire Bourbaki : volume 2005/2006, exposés 952-966, Astérisque, no. 311 (2007), Talk no. 957, pp. 123-135. http://www.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 778765 | Zbl 0558.05055

[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 2127609 | Zbl 1089.05027

[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 2233847 | Zbl 1112.05042

[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 815391 | Zbl 0674.05058

[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 1936646 | Zbl 1001.05061

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

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

[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 1957481 | Zbl 1030.05049

[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 2065897 | Zbl 1043.05096

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

[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. | Article | MR 2279669 | Zbl 1121.05052

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

[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 373947 | Zbl 0267.05119

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

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

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

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

[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 1666954 | Zbl 0933.05062

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

[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 1866394 | Zbl 1028.05036