The strong perfect graph theorem

Gérard Cornuéjols

Séminaire Bourbaki (2005-2006)

  • Volume: 48, page 123-136
  • ISSN: 0303-1179

Abstract

top
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.

How to cite

top

Cornuéjols, Gérard. "Le théorème fort des graphes parfaits." Séminaire Bourbaki 48 (2005-2006): 123-136. <http://eudml.org/doc/252154>.

@article{Cornuéjols2005-2006,
abstract = {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.},
author = {Cornuéjols, Gérard},
journal = {Séminaire Bourbaki},
keywords = {Perfect graph; Berge; strong perfect graph conjecture},
language = {fre},
pages = {123-136},
publisher = {Association des amis de Nicolas Bourbaki, Société mathématique de France},
title = {Le théorème fort des graphes parfaits},
url = {http://eudml.org/doc/252154},
volume = {48},
year = {2005-2006},
}

TY - JOUR
AU - Cornuéjols, Gérard
TI - Le théorème fort des graphes parfaits
JO - Séminaire Bourbaki
PY - 2005-2006
PB - Association des amis de Nicolas Bourbaki, Société mathématique de France
VL - 48
SP - 123
EP - 136
AB - 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.
LA - fre
KW - Perfect graph; Berge; strong perfect graph conjecture
UR - http://eudml.org/doc/252154
ER -

References

top
  1. [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. [2] M. Burlet & J. Fonlupt – “Polynomial algorithm to recognize a Meyniel graph”, Ann. Discrete Math.21 (1984), p. 225–252. Zbl0558.05055MR778765
  3. [3] M. Chudnovsky, G. Cornuéjols, X. Liu, P. Seymour & K. Vušković – “Recognizing Berge graphs”, Combinatorica 25 (2005), no. 2, p. 143–186. Zbl1089.05027MR2127609
  4. [4] M. Chudnovsky, N. Robertson, P. Seymour & R. Thomas – “Workshop on Graph Colouring and Decomposition”, exposé oral, Princeton, septembre 2001. 
  5. [5] —, “The strong perfect graph theorem”, Ann. of Math. (2) 164 (2006), no. 1, p. 51–229. Zbl1112.05042MR2233847
  6. [6] M. Chudnovsky & P. Seymour – communication personnelle, janvier 2002. 
  7. [7] —, communication personnelle, mai 2002. 
  8. [8] V. Chvátal – “Star-cutsets and perfect graphs”, J. Combin. Theory Ser. B 39 (1985), no. 3, p. 189–199. Zbl0674.05058MR815391
  9. [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. Zbl1001.05061MR1936646
  10. [10] V. Chvátal & N. Sbihi – “Recognizing claw-free perfect graphs”, J. Combin. Theory Ser. B 44 (1988), no. 2, p. 154–176. Zbl0669.05054MR930204
  11. [11] —, “Bull-free Berge graphs are perfect”, Graphs Combin. 3 (1987), no. 2, p. 127–139. Zbl0633.05056MR932129
  12. [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. Zbl1030.05049MR1957481
  13. [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. Zbl1043.05096MR2065897
  14. [14] —, “Square-free perfect graphs”, J. Combin. Theory Ser. B 90 (2004), no. 2, p. 257–307. Zbl1033.05047MR2034030
  15. [15] M. Conforti, G. Cornuéjols & G. Zambelli – “Decomposing Berge graphs containing no proper wheel, subdivided prism or their complements”, Combinatorica26 (2006), p. 533–558. Zbl1121.05052MR2279669
  16. [16] G. Cornuéjols & W. H. Cunningham – “Compositions for perfect graphs”, Discrete Math. 55 (1985), no. 3, p. 245–254. Zbl0562.05043MR802663
  17. [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. [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. Zbl0267.05119MR373947
  19. [19] G. S. Gasparian – “Minimal imperfect graphs : a simple approach”, Combinatorica 16 (1996), no. 2, p. 209–212. Zbl0858.05044MR1401893
  20. [20] D. König – “Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre”, Math. Ann. 77 (1916), no. 4, p. 453–465. Zbl46.0146.03MR1511872JFM46.0146.03
  21. [21] L. Lovász – “A characterization of perfect graphs”, J. Combinatorial Theory Ser. B13 (1972), p. 95–98. Zbl0241.05107MR309780
  22. [22] —, “Normal hypergraphs and the perfect graph conjecture”, Discrete Math. 2 (1972), no. 3, p. 253–267. Zbl0239.05111MR302480
  23. [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. Zbl0933.05062MR1666954
  24. [24] M. W. Padberg – “Perfect zero-one matrices”, Math. Programming6 (1974), p. 180–196. Zbl0284.90061MR340053
  25. [25] F. Roussel & P. Rubio – “About skew partitions in minimal imperfect graphs”, J. Combin. Theory Ser. B 83 (2001), no. 2, p. 171–190. Zbl1028.05036MR1866394

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.