×

zbMATH — the first resource for mathematics

Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs. (English) Zbl 1030.05049
A hole is a cordless cycle of length at least four. A hole is odd if it has an odd number of vertices. The strong perfect graph conjecture states that a graph \(G\) is perfect if neither \(G\) nor \(\overline G\) has an odd hole. The authors prove the conjecture for graphs that do not contain parachutes and proper wheels. Recently, M. Chudnovsky, N. Robertson, P. D. Seymoud and R. Thomas [Math. Program. 97B, 405-422 (2002; Zbl 1028.05035)] proved the conjecture for all graphs.

MSC:
05C17 Perfect graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[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. Natur. Reihe (1961) 114-115.
[2] Burlet, M.; Fonlupt, J., Polynomial algorithm to recognize a meyniel graph, Annals of discrete math., 21, 225-252, (1984) · Zbl 0558.05055
[3] M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, preprint (2002). · Zbl 1112.05042
[4] Chvátal, V., Star cutsets and perfect graphs, J. combin. theory B, 39, 189-199, (1985) · Zbl 0674.05058
[5] Conforti, M.; Cornuéjols, G.; Gasparyan, G.; Vušković, K., Perfect graphs, partitionable graphs and cutsets, Combinatorica, 22, 19-33, (2002) · Zbl 0996.05060
[6] M. Conforti, G. Cornuéjols, A. Kapoor, K. Vušković, in: E. Balas, J. Clausen (Eds.), A Mickey-Mouse Decomposition Theorem, Proceedings of the IV IPCO Conference, Lecture Notes in Computer Science 920 (1995) 321-328.
[7] Conforti, M.; Cornuéjols, G.; Kapoor, A.; Vušković, K., Even and odd holes in cap-free graphs, J. graph theory, 30, 289-308, (1999) · Zbl 0920.05028
[8] Conforti, M.; Gerards, B.; Kapoor, A., A theorem of truemper, Combinatorica, 20, 15-26, (2000) · Zbl 0949.05071
[9] Cornuéjols, G.; Cunningham, W.H., Compositions for perfect graphs, Discrete math., 55, 245-254, (1985) · Zbl 0562.05043
[10] Cunningham, W.H.; Edmonds, J., A combinatorial decomposition theory, Canad. J. math., 22, 734-765, (1980) · Zbl 0442.05054
[11] Harary, F.; Holtzmann, C., Line graphs of bipartite graphs, Rev. soc. mat. Chile, 1, 19-22, (1974)
[12] Maffray, F.; Reed, B., A description of claw-free perfect graphs, J. combin. theory B, 75, 134-156, (1999) · Zbl 0933.05062
[13] Meyniel, H., On the perfect graph conjecture, Discrete math., 16, 339-342, (1976) · Zbl 0383.05018
[14] Truemper, K., Alpha-balanced graphs and matrices and GF(3)-representability of matroids, J. combin. theory B, 32, 112-139, (1982) · Zbl 0478.05026
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.