×

Square-free perfect graphs. (English) Zbl 1033.05047

Summary: We prove that square-free perfect graphs are bipartite graphs or line graphs of bipartite graphs or have a 2-join or a star cutset.

MSC:

05C17 Perfect graphs
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] C. Berge, Färbung von Graphen deren sämtliche bzw. deren ungerade Kreise starr sind (Zusammenfassung), Wissenschaftliche Zeitschrift, Martin Luther Universität Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe (1961) 114-115.; C. Berge, Färbung von Graphen deren sämtliche bzw. deren ungerade Kreise starr sind (Zusammenfassung), Wissenschaftliche Zeitschrift, Martin Luther Universität Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe (1961) 114-115.
[2] M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, technical report, Princeton University, 2002.; M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, technical report, Princeton University, 2002. · Zbl 1112.05042
[3] Chvátal, V., Star cutsets and perfect graphs, J. Combin. Theory B, 39, 189-199 (1985) · Zbl 0674.05058
[4] Chvátal, V.; Fonlupt, J.; Sun, L.; Zemirline, A., Recognizing dart-free perfect graphs, SIAM Journal on Computing, 31, 1315-1338 (2002) · Zbl 1001.05061
[5] 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 (1999), J. Combin. Theory B, 87, 300-330 (2003) · Zbl 1030.05049
[6] Conforti, M.; Cornuéjols, G.; Kapoor, A.; Vušković, K., A Mickey Mouse decomposition theorem, (Balas, E.; Clausen, J., Proceedings of the Fourth International Integer Programming and Combinatorial Optimization Conference. Proceedings of the Fourth International Integer Programming and Combinatorial Optimization Conference, Lecture Notes in Computer Science, Vol. 920 (1995), Copenhagen: Copenhagen Denmark), 321-328 · Zbl 1500.05023
[7] Conforti, M.; Cornuéjols, G.; Kapoor, A.; Vušković, K., Even-hole-free graphs, Part Idecomposition theorem, J. Graph Theory, 39, 6-49 (2002) · Zbl 1005.05034
[8] Conforti, M.; Cornuéjols, G.; Kapoor, A.; Vušković, K., Balanced 0,± 1 matrices Idecomposition, J. Combin. Theory B, 81, 243-274 (2001) · Zbl 1026.05016
[9] Conforti, M.; Cornuéjols, G.; Kapoor, A.; Vušković, K., Balanced 0,± 1 matrices IIrecognition algorithm, J. Combin. Theory B, 81, 275-306 (2001) · Zbl 1026.05017
[10] Conforti, M.; Cornuéjols, G.; Rao, M. R., Decomposition of balanced matrices, J. Combin. Theory B, 77, 292-406 (1999) · Zbl 1023.05025
[11] Conforti, M.; Gerards, B.; Kapoor, A., A theorem of Truemper, Combin., 20, 1, 15-26 (2000) · Zbl 0949.05071
[12] Conforti, M.; Rao, M. R., Structural properties and decomposition of linear balanced matrices, Math. Programming, 55, 129-168 (1992) · Zbl 0767.90068
[13] Conforti, M.; Rao, M. R., Articulation sets in linear perfect matrices Iforbidden configurations and star cutsets, Discrete Math., 104, 23-47 (1992) · Zbl 0783.05070
[14] Conforti, M.; Rao, M. R., Articulation sets in linear perfect matrices IIthe wheel theorem and clique articulations, Discrete Math., 110, 81-118 (1992) · Zbl 0774.05064
[15] Cornuéjols, G., Combinatorial Optimization: Packing and Covering, CBMS-NSF Regional Conference Series in Applied Mathematics, Vol. 74 (2001), SIAM: SIAM Philadelphia · Zbl 0972.90059
[16] Cornuéjols, G.; Cunningham, W. H., Compositions for perfect graphs, Discrete Math., 55, 245-254 (1985) · Zbl 0562.05043
[17] J. Fonlupt, A. Zemirline, A polynomial recognition algorithm for perfect \(K_4e\); J. Fonlupt, A. Zemirline, A polynomial recognition algorithm for perfect \(K_4e\)
[18] J.-L. Fouquet, Perfect Graphs with no \(2K_2K_6\); J.-L. Fouquet, Perfect Graphs with no \(2K_2K_6\)
[19] J.F. Geelen, Matchings, Matroids and unimodular matrices, Ph.D. Thesis, University of Waterloo, 1995.; J.F. Geelen, Matchings, Matroids and unimodular matrices, Ph.D. Thesis, University of Waterloo, 1995.
[20] Hoàng, C. T., Some properties of minimal imperfect graphs, Discrete Math., 160, 165-175 (1996) · Zbl 0863.05055
[21] C. Linhares-Sales, F. Maffray, Even pairs in square-free Berge graphs, Laboratoire Leibniz Res. Rep. 51-2002, 2002.; C. Linhares-Sales, F. Maffray, Even pairs in square-free Berge graphs, Laboratoire Leibniz Res. Rep. 51-2002, 2002. · Zbl 1049.05041
[22] Meyniel, H., On the perfect graph conjecture, Discrete Math., 16, 339-342 (1976) · Zbl 0383.05018
[23] Meyniel, H., The graphs whose odd cycles have at least two chords, (Berge, C.; Chvatal, V., Topics on Perfect Graphs (1984), North-Holland: North-Holland Amsterdam), 115-120 · Zbl 0567.05034
[24] Olariu, S., Paw-free graphs, Information Processing Letters, 28, 53-54 (1988) · Zbl 0654.05063
[25] Parthasarathy, K. R.; Ravindra, G., The strong perfect graph conjecture is true for \(K_{1,3}\)-free graphs, J. Combin. Theory B, 21, 212-223 (1976) · Zbl 0297.05109
[26] Seinsche, D., On a property of the class of n-colorable graphs, J. Combin. Theory B, 16, 191-193 (1974) · Zbl 0269.05103
[27] Truemper, K., Alpha-balanced graphs and matrices and GF(3)-representability of matroids, J. Combin. Theory B, 32, 112-139 (1982) · Zbl 0478.05026
[28] Tucker, A., Critical perfect graphs and perfect 3-chromatic graphs, J. Combin. Theory B, 23, 143-149 (1977) · Zbl 0376.05047
[29] Tucker, A., Coloring perfect \((K_4\)-e)-free graphs, J. Combin. Theory B, 43, 313-318 (1987) · Zbl 0585.05007
[30] West, D. B., Introduction to Graph Theory (1996), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0845.05001
[31] Xue, Q., \((C_4\), Lotus)-free Berge graphs are perfect, An. Ştiinţ. Univ. Al. I. Cuza Iaşi Inform. (N.S.), 4, 65-71 (1995) · Zbl 0853.05042
[32] Xue, Q., On a class of square-free graphs, Inform. Process. Lett., 57, 47-48 (1996) · Zbl 1023.68648
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.