×

The strong perfect graph conjecture: 40 years of attempts, and its resolution. (English) Zbl 1191.05051

Summary: 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 significant 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, those 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, B. A. Reed (Eds.), Perfect Graphs, Wiley & Sons. (2001; Zbl 0972.00015)], but it also implies a deeper analysis (with additional results) and another viewpoint on the topic.

MSC:

05C17 Perfect graphs
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics

Citations:

Zbl 0972.00015
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bacsó, G.; Boros, E.; Gurvich, V.; Maffray, F.; Preissmann, M., On minimal imperfect graphs with circular symmetry, J. Graph Theory, 29, 209-225 (1998) · Zbl 0919.05029
[2] Berge, C., Les problémes de coloration en théorie des graphes, Publ. Inst. Stat. Univ. Paris, 9 (1960) · Zbl 0103.16201
[3] Bertschi, M. E.; Reed, B. A., Erratum: A note on even pairs [Discrete Math. 65 (1987) 317-318, by B. Reed], Discrete Math., 71, 187 (1988)
[4] Bixby, R. E., A composition for perfect graphs, (Berge, C.; Chvátal, V., Topics on Perfect Graphs. Topics on Perfect Graphs, Ann. Discrete Math., vol. 21 (1984), North-Holland: North-Holland Amsterdam), 221-224
[5] Bland, R. G.; Huang, H.-C.; Trotter, L. E., Graphical properties related to minimal imperfection, Discrete Math., 27, 11-22 (1979) · Zbl 0421.05028
[6] Boros, E.; Gurvich, V. A.; Hougardy, S., Recursive generation of partitionable graphs, J. Graph Theory, 41, 259-285 (2002) · Zbl 1018.05040
[7] Burlet, M.; Fonlupt, J., Polynomial algorithm to recognize a Meyniel graph, (Berge, C.; Chvátal, V., Topics on Perfect Graphs. Topics on Perfect Graphs, Ann. Discrete Math., vol. 21 (1984), North-Holland: North-Holland Amsterdam), 225-252 · Zbl 0558.05055
[8] Burlet, M.; Uhry, J. P., Parity graphs, (Berge, C.; Chvátal, V., Topics on Perfect Graphs. Topics on Perfect Graphs, Ann. Discrete Math., vol. 21 (1984), North-Holland: North-Holland Amsterdam), 253-278 · Zbl 0558.05036
[9] K. Cameron, Polyhedral and algorithmic ramifications of antichains, Ph.D. Thesis, University of Waterloo, 1982; K. Cameron, Polyhedral and algorithmic ramifications of antichains, Ph.D. Thesis, University of Waterloo, 1982
[10] Chudnovsky, M., Berge trigraphs, J. Graph Theory, 53, 1-55 (2006) · Zbl 1101.05036
[11] M. Chudnovsky, Berge trigraphs and their applications, Ph.D. Thesis, Princeton University, 2003; M. Chudnovsky, Berge trigraphs and their applications, Ph.D. Thesis, Princeton University, 2003
[12] Chudnovsky, M.; Cornuéjols, G.; Liu, X.; Seymour, P.; Vušković, K., Recognizing Berge graphs, Combinatorica, 25, 2, 143-186 (2005) · Zbl 1089.05027
[13] Chudnovsky, M.; Robertson, N.; Seymour, P. D.; Thomas, R., The Strong Perfect Graph Theorem, Ann. of Math., 164, 51-229 (2006) · Zbl 1112.05042
[14] Chvátal, V., On certain polytopes associated with graphs, J. Combin. Theory Ser. B, 18, 138-154 (1975) · Zbl 0277.05139
[15] V. Chvátal, Perfect problems, 2000. http://www.cs.concordia.ca/ chvatal/perfect/problems.html; V. Chvátal, Perfect problems, 2000. http://www.cs.concordia.ca/ chvatal/perfect/problems.html
[16] Chvátal, V., Star-cutsets and perfect graphs, J. Combin. Theory Ser. B, 39, 189-199 (1985) · Zbl 0674.05058
[17] Chvátal, V., On the strong perfect graph conjecture, J. Combin. Theory Ser. B, 20, 139-141 (1976) · Zbl 0293.05117
[18] Chvátal, V., Notes on perfect graphs, (Pulleybank, W. R., Progress in Combinatorial Optimization (1984), Academic Press: Academic Press Toronto, Ont), 107-115 · Zbl 0546.05027
[19] Chvátal, V.; Graham, R. L.; Perold, A. F.; Whitesides, S. H., Combinatorial designs related to the perfect graph conjecture, Discrete Math., 26, 83-92 (1979) · Zbl 0403.05017
[20] Chvátal, V.; Sbihi, N., Bull-free Berge graphs are perfect, Graphs Combin., 3, 127-139 (1987) · Zbl 0633.05056
[21] Chvátal, V.; Sbihi, N., Recognizing claw-free perfect graphs, J. Combin. Theory Ser. B, 44, 154-176 (1988) · Zbl 0669.05054
[22] Conforti, M.; Cornuéjols, G., 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, 300-330 (2003) · Zbl 1030.05049
[23] Conforti, M.; Cornuéjols, G.; Gasparyan, G.; Vuš ković, K., Perfect graphs, partitionable graphs and cutsets, Combinatorica, 22, 19-33 (2002) · Zbl 0996.05060
[24] Conforti, M.; Cornuéjols, G.; Kapor, A.; Vušković, K., Balanced \(0, \pm 1\) matrices, Part I: Decomposition theorem, and Part II: Recognition algorithm, J. Combin. Theory Ser. B, 81, 243-306 (2001)
[25] Conforti, M.; Cornuéjols, G.; Kapor, A.; Vušković, K., Even-hole-free graphs, Part I: Decomposition theorem, J. Graph Theory, 39, 6-49 (2002) · Zbl 1005.05034
[26] Conforti, M.; Cornuéjols, G.; Kapor, A.; Vušković, K., Even-hole-free graphs, Part II: Recognition algorithm, J. Graph Theory, 40, 238-266 (2002) · Zbl 1003.05095
[27] Conforti, M.; Cornuéjols, G.; Liu, X.; Vušković, K.; Zambelli, G., Odd hole recognition in graphs of bounded clique size, SIAM J. Discrete Math., 20, 1, 42-48 (2006) · Zbl 1110.05054
[28] Conforti, M.; Cornuéjols, G.; Rao, M. R., Decomposition of balanced matrices, J. Combin. Theory Ser. B, 77, 292-496 (1999) · Zbl 1023.05025
[29] Conforti, M.; Cornuéjols, G.; Vušković, K., Square-free perfect graphs, J. Combin. Theory Ser. B, 90, 2, 257-307 (2004) · Zbl 1033.05047
[30] Conforti, M.; Rao, M. R., Testing balancedness and perfection of linear matrices, Math. Program., 61, 1-18 (1993) · Zbl 0788.90062
[31] Corneil, D. G.; Fonlupt, J., Stable set bonding in perfect graphs and parity graphs, J. Combin. Theory Ser. B, 59, 1-14 (1993) · Zbl 0793.05119
[32] Cornuéjols, G., (Combinatorial Optimization: Packing and Covering. Combinatorial Optimization: Packing and Covering, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 74 (2001), SIAM)
[33] Cornuéjols, G.; Cunningham, B., Compositions for perfect graphs, Discrete Math., 55, 245-254 (1985) · Zbl 0562.05043
[34] Cornuéjols, G.; Reed, B. A., Complete multi-partite cutsets in minimal imperfect graphs, J. Combin. Theory Ser. B, 59, 191-198 (1993) · Zbl 0793.05120
[35] G. Cornuéjols, X. Liu, K. Vušković, A polynomial algorithm for recognizing perfect graphs, in: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 20-27; G. Cornuéjols, X. Liu, K. Vušković, A polynomial algorithm for recognizing perfect graphs, in: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 20-27
[36] Cunningham, W. H., Decomposition of directed graphs, SIAM J. Algebraic Discrete Methods, 3, 214-228 (1982) · Zbl 0497.05031
[37] Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71-76 (1961) · Zbl 0098.14703
[38] Edmonds, J., Path, trees, and flowers, Canadian J. Math., 17, 449-467 (1965) · Zbl 0132.20903
[39] Edmonds, J., Maximum matching and a polyhedron with (0, 1) vertices, J. Res. Natl. Bur. Stand., 69B, 125-130 (1965) · Zbl 0141.21802
[40] Edmonds, J.; Giles, R., A min-max relation for submodular functions on graphs, Ann. Discrete Math., 1, 185-204 (1977)
[41] de Figueiredo, C. M.H.; Klein, S.; Kohayakawa, Y.; Reed, B. A., Finding skew partitions efficiently, J. Algorithms, 37, 505-521 (2000) · Zbl 0964.68107
[42] Fonlupt, J.; Sebő, A., On the clique rank and the coloration of perfect graphs, (Kannan, R.; Pulleyblank, W. R., Integer Programming and Combinatorial Optimization (1990), Press, University of Waterloo), 201-229
[43] Fonlupt, J.; Uhry, J.-P., Transformations which preserve perfectness and H-perfectness of graphs, (Bonn Workshop on Combinatorial Optimization (Bonn, 1980). Bonn Workshop on Combinatorial Optimization (Bonn, 1980), Ann. Discrete Math., vol. 16 (1982), North-Holland: North-Holland Amsterdam, New York), 83-95 · Zbl 0502.05023
[44] Fonlupt, J.; Zemirline, A., A polynomial algorithm for recognizing \(K_4 - e\)-free perfect graphs, Rev. Maghrébine Math., 2, 1-26 (1993)
[45] Fulkerson, D. R., Anti-blocking polyhedra, J. Combin. Theory Ser. B, 12, 50-71 (1972) · Zbl 0227.05015
[46] Gallai, T., Graphen mit trianguleirbaren ungeraden Vielecken, Magyar Tud. Akad. Mat. Kutako Int. Közl, 7, 3-36 (1962) · Zbl 0132.21101
[47] Gasparyan, G. S., Minimal imperfect graphs: A simple approach, Combinatorica, 16, 209-212 (1996) · Zbl 0858.05044
[48] Gavril, F., Algorithms on clique separable graphs, Discrete Math., 19, 159-165 (1977) · Zbl 0378.05042
[49] Grinstead, C., On circular critical graphs, Discrete Math., 51, 11-24 (1984) · Zbl 0544.05028
[50] Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197 (1981) · Zbl 0492.90056
[51] Grötschel, M.; Lovász, L.; Schrijver, A., Polynomial algorithms for perfect graphs, (Berge, C.; Chvátal, V., Topics on Perfect Graphs. Topics on Perfect Graphs, Ann. Discrete Math., vol. 21 (1984), North-Holland: North-Holland Amsterdam), 325-356 · Zbl 0554.05041
[52] Grötschel, M.; Lovász, L.; Schrijver, A., Relaxation of vertex packing, J. Combin. Theory Ser. B, 40, 330-343 (1986) · Zbl 0596.05052
[53] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (1988), Springer-Verlag: Springer-Verlag Berlin, New York · Zbl 0634.05001
[54] V.A. Gurvich, V. Udalov, Berge strong perfect graph conjecture holds for the graphs with less than 25 vertices, Manuscript, 1992; V.A. Gurvich, V. Udalov, Berge strong perfect graph conjecture holds for the graphs with less than 25 vertices, Manuscript, 1992
[55] Gyárfás, A., Problems from the world surrounding perfect graphs, Proceedings of the International Conference on Combinatorial Analysis and its Applications. Proceedings of the International Conference on Combinatorial Analysis and its Applications, Zastos. Mat., 19, 413-441 (1987) · Zbl 0718.05041
[56] Hayward, R., Weakly triangulated graphs, J. Combin. Theory Ser. B, 39, 200-208 (1985) · Zbl 0551.05055
[57] Hoáng, C. T., Some properties of minimal imperfect graphs, Discrete Math., 160, 165-175 (1996) · Zbl 0863.05055
[58] Hoáng, C. T.; McDiarmid, C., On the divisibility of graphs, Discrete Math., 242, 145-156 (2002) · Zbl 0988.05068
[59] S. Hougardy, Counterexamples to three conjectures concerning perfect graphs, Technical Report RR870-M, Laboratoire Artemis-IMAG, Universitá Joseph Fourier, Grenoble, France, 1991; S. Hougardy, Counterexamples to three conjectures concerning perfect graphs, Technical Report RR870-M, Laboratoire Artemis-IMAG, Universitá Joseph Fourier, Grenoble, France, 1991 · Zbl 0795.05059
[60] Hougardy, S., Even pairs and the strong perfect graph conjecture, Discrete Math., 154, 277-278 (1996) · Zbl 0848.05055
[61] Hsu, W.-L., Decomposition of perfect graphs, J. Combin. Theory Ser. B, 43, 70-94 (1987) · Zbl 0587.05037
[62] Hsu, W.-L., Recognizing planar perfect graphs, J. Assoc. Comput. Mach., 34, 255-288 (1987)
[63] Jansen, K., A new characterization for parity graphs and a coloring problem with costs, (LATIN’98: Theoretical Informatics. LATIN’98: Theoretical Informatics, Lecture Notes in Computer Science, vol. 1380 (1998)), 249-260 · Zbl 0910.05028
[64] Lovász, L., A characterization of perfect graphs, J. Combin. Theory Ser. B, 13, 95-98 (1972) · Zbl 0241.05107
[65] Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2, 253-267 (1972) · Zbl 0239.05111
[66] Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25, 1-7 (1979) · Zbl 0395.94021
[67] Lovász, L., (Beineke, L. W.; Wilson, R. J., Perfect Graphs. Perfect Graphs, Selected Topics in Graph Theory, vol. 2 (1983), Academic Press: Academic Press London)
[68] Lovász, L.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 166-190 (1991) · Zbl 0754.90039
[69] Maffray, F.; Preissmann, M., Split neighbourhood graphs and the strong perfect graph conjecture, J. Combin. Theory Ser. B, 63, 294-309 (1995) · Zbl 0820.05023
[70] Maffray, F.; Preissmann, M., Perfect graphs with no \(P_5\) and \(K_5\), Graphs Combin., 10, 179-184 (1994) · Zbl 0806.05052
[71] Markosyan, S. E.; Karapetyan, I. A., Perfect graphs, Akad. Nauk Armjan. SSR Dokl., 63, 292-296 (1976), (in Russian with an Armenian summary)
[72] Meyniel, H., The graphs whose odd cycles have at least two chords, (Berge, C.; Chvátal, V., Topics on Perfect Graphs. Topics on Perfect Graphs, Ann. Discrete Math., vol. 21 (1984), North-Holland: North-Holland Amsterdam), 115-120 · Zbl 0567.05034
[73] Meyniel, H., A new property of critical imperfect graphs and some consequences, European J. Combin., 8, 313-316 (1987) · Zbl 0647.05053
[74] Padberg, M. W., Perfect zero-one matrices, Math. Program., 6, 180-196 (1974) · Zbl 0284.90061
[75] Padberg, M. W., Almost integral polyhedra related to certain combinatorial optimization problems, Linear Algebra Appl., 15, 69-88 (1976) · Zbl 0362.90077
[76] Papadimitriou, C. H.; Yannakakis, M., On recognizing integer polyhedra, Combinatorica, 10, 107-109 (1990) · Zbl 0718.68044
[77] Parthasarathy, K. R.; Ravindra, G., The strong perfect graph conjecture is true for \(K_{1, 3}\)-free graphs, J. Combin. Theory Ser. B, 21, 212-223 (1976) · Zbl 0297.05109
[78] Parthasarathy, K. R.; Ravindra, G., The strong perfect graph conjecture is true for \((K_4 - e)\)-free graphs, J. Combin. Theory Ser. B, 26, 98-100 (1979) · Zbl 0416.05062
[79] A. Pêcher, Graphes de cayley partitionnables. Ph.D. Thesis, University of Orleans, France, 2000; A. Pêcher, Graphes de cayley partitionnables. Ph.D. Thesis, University of Orleans, France, 2000
[80] Preissmann, M.; Sebő, A., Some aspects of minimal imperfect graphs, (Ramirez-Alfonsin, J. L.; Reed, B. A., Perfect Graphs (2001), Wiley & Sons), 185-214 · Zbl 0990.05055
[81] (Ramirez-Alfonsin, J. L.; Reed, B. A., Perfect Graphs (2001), Wiley & Sons)
[82] B.A. Reed, A semi-strong perfect graph theorem, Ph.D. Thesis, Department of Computer Science, Mc Gill University, Montréal, Québec, Canada, 1986; B.A. Reed, A semi-strong perfect graph theorem, Ph.D. Thesis, Department of Computer Science, Mc Gill University, Montréal, Québec, Canada, 1986 · Zbl 0647.05052
[83] Roussel, F.; Rubio, Ph., About skew partitions in minimal imperfect graphs, J. Combin. Theory Ser. B, 83, 171-190 (2001) · Zbl 1028.05036
[84] Roussel, F.; Rusu, I., Holes and dominoes in Meyniel graphs, Internat. J. Found. Comput. Sci., 10, 127-146 (1999) · Zbl 1320.05097
[85] Rusu, I., Building counterexamples, Discrete Math., 171, 213-227 (1997) · Zbl 0874.05024
[86] Rusu, I., Cutsets in perfect and minimal imperfect graphs, (Ramirez-Alfonsin, J. L.; Reed, B. A., Perfect Graphs (2001), Wiley & Sons), 167-183 · Zbl 0984.05039
[87] Sachs, H., On the Berge conjecture concerning perfect graphs, (Combinatorial Structures and their Applications (1969), Gordon and Beach: Gordon and Beach New York), 377-384
[88] Sakuma, T., A counterexample to the Bold Conjecture, J. Graph Theory, 25, 165-168 (1997) · Zbl 0874.05025
[89] Sassano, A., Chair-free Berge graphs are perfect, Graphs Combin., 13, 369-395 (1997) · Zbl 0891.05054
[90] Schenkman, E., Group Theory (1965), Van Nostrand: Van Nostrand Princeton, NJ · Zbl 0133.27302
[91] Schrijver, A., Polyhedral combinatorics, (Graham, R.; Grötschel, M.; Lovász, L., Handbook of Combinatorics (1995), Elsevier, North Holland), 1650-1704 · Zbl 0845.90103
[92] Sebő, A., On critical edges and minimal imperfect graphs, J. Combin. Theory Ser. B, 67, 62-85 (1996) · Zbl 0855.05062
[93] SebHo, A., Forcing colorations and the strong perfect graph conjecture, (Balas, E.; Cornuejols, G.; Kannan, R., Integer Programming and Combinatorial Optimization II (1992), Carnegie-Mellon University Press), 431-445
[94] Sebő, A., The connectivity of minimal imperfect graphs, J. Graph Theory, 23, 77-85 (1996) · Zbl 0859.05058
[95] Seinsche, D., On a property of the class of \(n\)-colorable graphs, J. Combin. Theory Ser. B, 16, 191-193 (1974) · Zbl 0269.05103
[96] Seymour, P., Decomposition of regular matroids, J. Combin. Theory Ser. B, 28, 305-359 (1980) · Zbl 0443.05027
[97] Seymour, P., How the proof of the strong perfect graph conjecture was found, Gazette des Mathématiciens, 109, 69-83 (2006) · Zbl 1189.05068
[98] Shepherd, F. B., Near-perfect matrices, Math. Program., 64, 295-323 (1994) · Zbl 0804.05036
[99] Shepherd, F. B., The theta body and imperfection, (Ramirez-Alfonsin, J. L.; Reed, B. A., Perfect Graphs (2001), Wiley & Sons), 261-291 · Zbl 1076.05511
[100] Tucker, A., Critical perfect graphs and perfect 3-chromatic graphs, J. Combin. Theory Ser. B, 23, 313-318 (1977)
[101] Tucker, A., On Berge’s strong perfect graph conjecture, Ann. New York Acad. Sci., 319, 530-535 (1979)
[102] Tucker, A., Uniquely colorable perfect graphs, Discrete Math., 44, 187-194 (1983) · Zbl 0508.05037
[103] Tucker, A., Coloring graphs with stable cutsets, J. Combin. Theory Ser. B, 34, 258-267 (1983) · Zbl 0498.05028
[104] Tucker, A., Coloring \((K_4 - e)\)-free graphs, J. Combin. Theory Ser. B, 42, 313-318 (1987) · Zbl 0585.05007
[105] A. Wagler, Rank-perfect and weakly rank-perfect graphs, ZIB-Report 01-18, 1-27, 2001; A. Wagler, Rank-perfect and weakly rank-perfect graphs, ZIB-Report 01-18, 1-27, 2001
[106] A. Wagler, Relaxing perfectness: Which graphs are almost perfect? ZIB-Report 02-03, 1-24, 2003; A. Wagler, Relaxing perfectness: Which graphs are almost perfect? ZIB-Report 02-03, 1-24, 2003
[107] Whitesides, S. H., Solving certain graphs recognition and optimization problems with applications to perfect graphs, (Berge, C.; Chvátal, V., Topics on Perfect Graphs. Topics on Perfect Graphs, Ann. Discrete Math., vol. 21 (1984), North-Holland: North-Holland Amsterdam), 281-297
[108] G. Zambelli, On Perfect Graphs and Balanced Matrices, Dissertation at Carnegie Mellon University, Pittsburgh, PA, 2004; G. Zambelli, On Perfect Graphs and Balanced Matrices, Dissertation at Carnegie Mellon University, Pittsburgh, PA, 2004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.