×

zbMATH — the first resource for mathematics

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
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), 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. · 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, (), 321-328
[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 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 K4-{e}-free graphs, Rapport Technique RT-16, Artemis, IMAG, Grenoble, France, 1987.
[18] J.-L. Fouquet, Perfect Graphs with no 2K2 and no K6, Technical Report, Universite du Maine, Le Mans, France, 1999.
[19] 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. · 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, (), 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 K1,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 (K4-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 Englewood Cliffs, NJ · Zbl 0845.05001
[31] Xue, Q., (C4, 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. 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.