\documentstyle[11pt]{article} \pagestyle{plain} \setlength{\textwidth}{7.3in} \setlength{\textheight}{9.5in} \setlength{\oddsidemargin}{-0.5in} \setlength{\topmargin}{-1in} \begin{document} \bibliographystyle{alpha} Here is a bibliography of papers on perfect graphs; Wenan Zang of RUTCOR has helped very much in its preparation. Please, send a list of your own papers (and papers that they refer to) that should be included here but as yet are not by e-mail to \begin{center} {\tt chvatal@dimacs.rutgers.edu} \end{center} or by ordinary mail to \begin{center} Va\v{s}ek Chv\'atal, Dept. Computer Science, Rutgers University,\\ New Brunswick, NJ 08903, USA. \end{center} Please, try to follow the style used here; if you can, include the Mathematical Reviews numbers. \medskip I have not developed clear-cut criteria for what to include and what to exclude. My rough guiding principle was to include only papers that bear directly on Claude Berge's Strong Perfect Graph Conjecture and/or the problem of recognizing perfect graphs in polynomial time. Thus I was led to exclude, for instance, papers specializing in interval graphs: these are special triangulated graphs and we know all we could wish about the wider class. Please, bear in mind that the line has to be drawn somewhere: to take just one example, I don't think we want the bibliography overflowing with papers on partially ordered sets, even though one could argue that these are papers on comparability graphs. One more thing: I have been excluding preprints and theses on the grounds that pointers to not easily accessible documents are often more frustrating than helpful.\\ Thanks to all who have contributed. \bigskip \begin{thebibliography}{100} \bibitem{} J.~Akiyama and V.~Chv\'atal, {\em Packing paths perfectly}, Discrete Math. {\bf 85} (1990), 247--255, MR 92a:68114. \bibitem{} T.~Andreae, M.~Schughart, and Zs.~Tuza, {\em Clique-transversal sets of line graphs and complements of line graphs}, Discrete Math. {\bf 88} (1991), 11--20, MR 92a:05100. \bibitem{} R.~P.~Anstee and M.~Farber, {\em Characterizations of totally balanced matrices}, J. Algorithms {\bf 5} (1984), 215-230, MR 86e:05019. \bibitem{} J.-C.~Arditti and D.~de~Werra, {\em A note on a paper by {D}. {S}einsche}, J. Combin. Theory Ser. B {\bf 21} (1976), 90, MR 54 \#2510. \bibitem{} C.~Berge, {\em Les probl\`{e}mes de coloration en th\'{e}orie des graphes}, Publ. Inst. Stat. Univ. Paris {\bf 9} (1960), 123--160, MR 23 \#A1551. \bibitem{} G.~Bacs\'o and Zs.~Tuza, {\em Dominating cliques in $P_5$-free graphs}, Period. Math. Hungar. {\bf 21} (1990), 303-308, MR 92g:05150. \bibitem{} G.~Bacs\'o and Zs.~Tuza, {\em A characterization of graphs without long induced paths}, J. Graph Theory {\bf 14} (1990), 455-464, MR 91f:05092. \bibitem{} G.~Bacs\'o and Zs.~Tuza, {\em Domination properties and induced subgraphs}, Discrete Math. {\bf 111} (1993), 37-40. \bibitem{} G.~Bacs\'o and Zs.~Tuza, {\em Dominating subgraphs of small diameter}, J. Combin. Inform. System Sci. {\bf 17} (1992), in print. \bibitem{} C.~Berge, {\em F\"arbung von {G}raphen, deren s\"amtliche bzw. deren ungeraden {K}reise starr sind ({Z}usammenfassung)}, Math. - Natur. Reihe {\bf 114} (1961). \bibitem{} C.~Berge, {\em Sur une conjecture relative au probl\`eme des codes optimaux}, manuscript distributed at the 14th General Meeting of the International Institute of Radio Science, Tokyo, 1963. \bibitem{} C.~Berge, {\em Une application de la th\'eorie des graphes \`a un probl\`eme de codage}, in Automata Theory (E.~R.~Caianiello, ed.), Academic Press, New York, 1966, pp.~25--34, MR 43 \#83. \bibitem{} C.~Berge, {\em Some classes of perfect graphs}, in Graph Theory and Theoretical Physics (F.~Harary, ed.), Academic Press, London, 1967, pp.~155--165, MR 38 \#1017. \bibitem{} C.~Berge, {\em The rank of a family of sets and some applications to graph theory}, in Recent Progress in Combinatorics (W.~T.~Tutte, ed.), Academic Press, New York, 1969, pp.~49--57, MR 41 \#5231. \bibitem{} C.~Berge, {\em Some classes of perfect graphs}, in Combinatorial Mathematics and its Applications (R.~C.~Bose and T.~A.~Dowling, eds.), Univ. North Carolina Press, Chapel Hill, N.C., 1969, pp.~539--552, MR 42 \# 100. \bibitem{} C.~Berge, {\em Balanced matrices}, Math. Programming {\bf 2} (1972), 19--31, MR 48 \#142. \bibitem{} C.~Berge, {\em Balanced hypergraphs and some applications to graph theory}, in A Survey of Combinatorial Theory (J.~N.~Srivastava, ed.), North-Holland, Amsterdam, 1973, pp.~15--23, MR 51 \#2970. \bibitem{} C.~Berge, {\em Perfect graphs}, in Studies in Graph Theory, Part I (D. R. Fulkerson, ed.), M.A.A. Studies in Mathematics {\bf 11} (1975), 1--22, MR 53 \#10585. \bibitem{} C.~Berge, {\em Balanced matrices and property {G}}, Math. Programming Stud. {\bf 12} (1980), 163--175, MR 82d:05080. \bibitem{} C.~Berge, {\em Diperfect graphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 45--56, MR 86m:05047. \bibitem{} C.~Berge, {\em Minimax theorems for normal hypergraphs and balanced hypergraphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 3--20, MR 86m:05107. \bibitem{} C.~Berge, {\em The q-perfect graphs I: The case q=2}, in Sets, Graphs and Numbers (L.~Lov\'asz, D.~Miklos, and T.~Sz\"onyi, eds.), North-Holland, Amsterdam, to appear. \bibitem{} C.~Berge, {\em The q-perfect graphs II}, RUTCOR Research Report 23-92, Rutgers University, July 1992. \bibitem{} C.~Berge and V.~Chv\'{a}tal (eds.), {\em Topics on Perfect Graphs}, Math. stud. 88, North-Holland, Amsterdam-New York-Oxford, 1984, MR 85k:05006. \bibitem{} C.~Berge, C.~C.~Chen, V.~Chv\'atal, and C.~S.~Seow, {\em Combinatorial properties of polyominoes}, Combinatorica {\bf 1} (1981), 217--224, MR 83b:05051. \bibitem{} C.~Berge and P.~Duchet, {\em Strongly perfect graphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 57--62, MR 86g:05077. \bibitem{} C.~Berge and P.~Duchet, {\em Perfect graphs and kernels}, Bull. Inst. Math. Acad. Sinica {\bf 16} (1988), 263-274, MR 91a:05048. \bibitem{} C.~Berge and P.~Duchet, {\em Recent problems and results about kernels in directed graphs}, Discrete Math. {\bf 86} (1990), 27-31, MR 91m:05091. \bibitem{} C.~Berge and M.~Las Vergnas, {\em Sur une th\'eor\`eme du type {K}\"onig pour hypergraphes}, Ann. N.Y. Acad. Sci. {\bf 175} (1970), 32--40, MR 42 \#1690. \bibitem{} M.~Bertschi, {\em Perfectly contractile graphs}, J. Combin. Theory Ser. B {\bf 50} (1990), 222--230, MR 91j:05042. \bibitem{} M.~Bertschi and B.~A. Reed, {\em A note on even pairs}, Discrete Math. {\bf 65} (1987), 317--318, MR 88f:05066. \bibitem{} D.~Bienstock, {\em On the complexity of testing for odd holes and odd induced paths}, Discrete Math. {\bf 90} (1991), 85--92, MR 92m:68040a. Corrigendum in Discrete Math. {\bf 102} (1992), 109. \bibitem{} R.~E. Bixby, {\em A composition for perfect graphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 221--224, MR 86f:05105. \bibitem{} R.~G. Bland, H.-C.~Huang, and L.~E.~Trotter, Jr., {\em Graphical properties related to minimal imperfection}, Discrete Math. {\bf 27} (1979), 11--22, MR 80g:05034. \bibitem{} R.~G. Bland, H.-C.~Huang, and L.~E.~Trotter, Jr., {\em Graphical properties related to minimal imperfection}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 181--192, MR 86e:05075. \bibitem{} M.~Blidia, {\em A parity digraph has a kernel}, Combinatorica {\bf 6} (1986), 23-27, MR 88e:05046. \bibitem{} M.~Blidia, P.~Duchet, and F.~Maffray, {\em On the orientation of perfect graphs}, RUTCOR Research Report 4-88, Rutgers University, 1988. \bibitem{} M.~Blidia, P.~Duchet, and F.~Maffray, {\em On the orientation of Meyniel graphs}, RUTCOR Research Report 3-90, Rutgers University, 1990. \bibitem{} M.~Blidia and K.~Engel, {\em Perfectly orderable graphs and almost all perfect graphs are kernel M-solvable}, Graphs Combin. {\bf 8} (1992), 103-108. \bibitem{} F.~Bories and J.-L.~Jolivet, {\em On complete colorings of graphs}, in Recent Advances in Graph Theory (Proc. Second Czechoslovak Sympos., Prague, 1974), Academia, Prague, 1975, MR 52 \#5463. \bibitem{} M.~A.~Buckingham and M.~C.~Golumbic, {\em Partitionable graphs, circle graphs and the Berge strong perfect graph conjecture}, Discrete Math. {\bf 44} (1983), 45-54, MR 84g:05119. \bibitem{} P.~Buneman, {\em A characterization of rigid circuit graphs}, Discrete Math. {\bf 9} (1974), 205--212, MR 50 \#9686. \bibitem{} M.~Burlet and J.~Fonlupt, {\em Polynomial algorithm to recognize a {M}eyniel graph}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 225--252, MR 86h:05090. \bibitem{} M.~Burlet and J.~P. Uhry, {\em Parity graphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 253--278, MR 86i:05116. \bibitem{} K.~G.~Cameron, {\em Polyhedral and algorithmic ramifications of antichains}, Ph.D. thesis, University of Waterloo, 1982. \bibitem{} K.~G.~Cameron, {\em A minimax relation for the partial q-colorings of a graph: Box perfection}, Discrete Math. {\bf 74} (1989), 15-27, MR 90c:05081. \bibitem{} K.~G.~Cameron, J.~Edmonds, and L.~Lov\'asz, {\em A note on perfect graphs}, Period. Math. Hung. {\bf 17} (1986), 173--175, MR 87i:05093. \bibitem{} O.~M.~Carducci, {\em The strong perfect graph conjecture holds for diamonded odd cycle-free graphs}, Discrete Math. {\bf 110} (1992), 17--34. \bibitem{} C.~Champetier, {\em Kernels in some orientations of comparability graphs}, J. Combin. Theory Ser. B {\bf 47} (1989), 111-113, MR 90g:05081. \bibitem{CFT} G.~J.~Chang, M.~Farber, and Zs.~Tuza, {\em Algorithmic aspects of neighborhood numbers}, SIAM J. Discrete Math. {\bf 6} (1993), 24-29. \bibitem{} V.~Chv\'atal, {\em On certain polytopes associated with graphs}, J. Combin. Theory Ser. B {\bf 18} (1975), 138--154, MR 51 \#7949. \bibitem{} V.~Chv\'atal, {\em On the strong perfect graph conjecture}, J. Combin. Theory Ser. B {\bf 20} (1976), 139--141, MR 54 \#129. \bibitem{} V.~Chv\'atal, {\em An equivalent version of the strong perfect graph conjecture}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 193--196, MR 86j:05058. \bibitem{} V.~Chv\'atal, {\em Perfectly ordered graphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 63--66, MR 86j:05059. \bibitem{} V.~Chv\'atal, {\em A semi-strong perfect graph conjecture}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 279--280, MR 86j:05119. \bibitem{} V.~Chv\'atal, {\em Notes on perfect graphs}, in Progress in Combinatorial Optimization (W.~R.~Pulleyblank, ed.), Academic Press, 1984, pp. 107-115, MR 86h:05091. \bibitem{} V.~Chv\'atal, {\em Recent results on perfect graphs}, in International Symposium on Circuits and Systems Proceedings, The IEEE Circuits and Systems Society, 1985, pp. 1183--1186. \bibitem{} V.~Chv\'atal, {\em Star-cutsets and perfect graphs}, J. Combin. Theory Ser. B {\bf 39} (1985), 189--199, MR 87a:05060. \bibitem{} V.~Chv\'atal, {\em On the $P_4$-structure of perfect graphs {I}{I}{I}. {P}artner decompositions}, J. Combin. Theory Ser. B {\bf 43} (1987), 349--353, MR 89a:05062. \bibitem{} V.~Chv\'atal, {\em Perfect graphs}, in Surveys in Combinatorics 1987 (C.~Whitehead, ed.), LMS Lecture Notes 123, Cambridge University Press, 1987, pp. 43--51, MR 88k:05079. \bibitem{} V.~Chv\'atal, {\em Which line-graphs are perfectly orderable?} J. Graph Theory {\bf 14} (1990), 247--255, MR 92a:05105. \bibitem{} V.~Chv\'atal and C.~Ebenegger, {\em A note on line digraphs and the directed max-cut problem}, Discrete Appl. Math. {\bf 29} (1990), 165--170, MR 91i:05059. \bibitem{} V.~Chv\'atal, R.~L. Graham, A.~F. Perold, and S.~H. Whitesides, {\em Combinatorial designs related to the strong perfect graph conjecture}, Discrete Math. {\bf 26} (1979), 83--92, MR 81b:0544. \bibitem{} V.~Chv\'atal, {\em Combinatorial designs related to the strong perfect graph conjecture}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 197--206, MR 87f:05067. \bibitem{} V.~Chv\'atal and C.~T. Ho\`{a}ng, {\em On the $P_4$-structure of perfect graphs {I}. {E}ven decompositions}, J. Combin. Theory Ser. B {\bf 39} (1985), 209--219, MR 87c:05056a. \bibitem{} V.~Chv\'atal, C.~T. Ho\`{a}ng, N.~V.~R.~Mahadev, and D.~de~Werra, {\em Four classes of perfectly orderable graphs}, J. Graph Theory {\bf 11} (1987), 481--495, MR 88i:05079. \bibitem{} V.~Chv\'atal, W.~J.~Lenhart, and N.~Sbihi, {\em Two-colorings that decompose perfect graphs}, J. Combin. Theory Ser. B {\bf 49} (1990), 1--9, MR 91f:05051. \bibitem{} V.~Chv\'atal and N.~Sbihi, {\em Bull-free {B}erge graphs are perfect}, Graphs Combin. {\bf 3} (1987), 127--139, MR 89a:05063. \bibitem{} V.~Chv\'atal and N.~Sbihi, {\em Recognizing claw-free perfect graphs}, J. Combin. Theory Ser. B {\bf 44} (1988), 154--176, MR 89e:05165. \bibitem{} M.~Conforti, {\em ($K_4 -e$)-free perfect graphs and star cuts}, in Combinatorial Optimization 1403, Lecture Notes in Math., Springer, Berlin, 1989, 236-253, MR 91c:05078. \bibitem{} M.~Conforti, G.~Cornu\'{e}jols, and M.~R.~Rao, {\em Decomposition of balanced 0-1 matrices}, mimeo Carnegie Mellon, October 1991, to appear. \bibitem{} D.~Corneil, {\em Families of graphs complete for the strong perfect graph conjecture}, J. Graph Theory {\bf 10} (1986), 33--40, MR 87h:05160. \bibitem{} D.~Corneil, H.~Lerchs, and L.~S.~Burlingham, {\em Complement reducible graphs}, Discrete Appl. Math. {\bf 3} (1981), 163--174, MR 84d:05137. \bibitem{} D.~Corneil, Y.~Perl, and L.~Stewart, {\em A linear recognition algorithm for cographs}, SIAM J. Comput. {\bf 14} (1985), 926--934, MR 86m:68117. \bibitem{} G.~Cornu\'{e}jols and W.~H.~Cunningham, {\em Composition for perfect graphs}, Discrete Math. {\bf 55} (1985), 245--254, MR 86j:05120. \bibitem{} I.~Csisz\'{a}r, J.~K\"orner, L.~Lov\'asz, K.~Marton, and G.~Simonyi, {\em Entropy splitting for antiblocking pairs and perfect graphs}, Combinatorica {\bf 10} (1990), 27--40, MR 92a:05093. \bibitem{} C.~Croitoru and C.~Radu, {\em Submodularity relations for the independence function of a graph}, Ann. \c{S}tiint. Univ. ``Al. I. Cuza'' Ia\c{s}i Sect. Inform. {\bf 1} (1992), 3--11. \bibitem{} C.~Croitoru and C.~Radu, {\em Orderings and colorings in a graph}, Ann. \c{S}tiint. Univ. ``Al. I. Cuza'' Ia\c{s}i Sect. Inform. {\bf 1} (1992), 11--16. \bibitem{} R.~C.~Dalang, L.~E.~Trotter Jr., and D.~de~Werra, {\em On randomized stopping points and perfect graphs}, J. Combin. Theory Ser. B {\bf 45} (1988), 320--344, MR 90b:05120. \bibitem{} C.~De~Simone and A.~Galluccio, {\em New classes of Berge perfect graphs}, Discrete Math. (1992), to appear. \bibitem{} D.~de Werra, {\em On line perfect graphs}, Math. Programming {\bf 15} (1978), 236-238, MR 81a:05052. \bibitem{} D.~de~Werra and A.~Hertz, {\em On perfectness of sums of graphs}, Report ORWP 87/13, Swiss Federal Institute of Technology in Lausanne, 1987. \bibitem{} R.~P. Dilworth, {\em A decomposition theorem for partially ordered sets}, Ann. Math. Ser. 2 {\bf 51} (1950), 161--166, MR 11 \#309. \bibitem{} G.~A. Dirac, {\em On rigid circuit graphs}, Abh. Math. Sem Univ. Hamburg {\bf 25} (1961), 71--76, MR 24 \#A57. \bibitem{} P.~Duchet, {\em Graphes noyaux-parfaits}, Ann. Discrete Math. {\bf 9} (1980), 93-101, MR 81k:05051. \bibitem{} P.~Duchet, {\em Classical perfect graphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 67--98, MR 86b:05029. \bibitem{} P.~Duchet, {\em Parity graphs are kernel-M-solvable}, J. Combin. Theory Ser. B {\bf 43} (1987), 121-126, MR 88j:05018. \bibitem{} P.~Duchet, {\em A sufficient condition for a graph to be kernel-perfect}, J. Graph Theory {\bf 11} (1987), 81-86, MR 88c:05059. \bibitem{} P.~Duchet and H.~Meyniel, {\em A note on kernel-critical graphs}, Discrete Math. {\bf 33} (1981), 103-105, MR 81k:05052. \bibitem{} P.~Duchet and H.~Meyniel, {\em Une g\'{e}n\'{e}ralisation du th\'{e}or\`{e}me de Richardson sur l'existence de noyaux dans le graphs orient\'{e}s}, Discrete Math. {\bf 43} (1983), 21-27, MR 84g:05067. \bibitem{} M.~R.~Farber, {\em Characterizations of strongly chordal graphs}, Discrete Math. {\bf 43} (1983), 173-189, MR 84c:05072. \bibitem{} J.~Fonlupt and J.~P.~Uhry, {\em Transformations which preserve perfection and H-perfection of graphs}, in Bonn Workshop on Combinatorial Optimization, North-Holland, Amsterdam - New York, 1982, pp. 83-95, MR 84f:05076. \bibitem{} J.~Fonlupt and A.~Seb\H o, {\em On the clique rank and the coloration of perfect graphs}, in Integer Programming and Combinatorial Optimization {\bf 1} (R.~Kannan and W.~R.~Pulleyblank, eds.), University of Waterloo Press, 1990, pp.~201-229. \bibitem{} J.-C.~Fournier and M.~Las Vergnas, {\em Une classe d'hypergraphes bichromatiques}, Discrete Math. {\bf 2} (1972), 407--410, MR 46 \#5156. \bibitem{} J.-C.~Fournier and M.~Las Vergnas, {\em Une classe d'hypergraphes bichromatiques {I}{I}}, Discrete Math. {\bf 7} (1974), 99--106, MR 49 \#2446. \bibitem{} J.-C.~Fournier and M.~Las Vergnas, {\em A class of bichromatic hypergraphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 21--28, MR 86h:05080. \bibitem{} A.~Frank, {\em Some polynomial algorithms for certain graphs and hypergraphs}, Proc. Fifth British Comb. Conf. (Aberdeen, 1975), Congressus Numerantium 15, Utilitas Math. (Winnipeg), 1976, pp.~211--226, MR 52 \#13500. \bibitem{} D.~R. Fulkerson, {\em Note on {D}ilworth's decomposition theorem for partially ordered sets}, Proc. Amer. Math. Soc. {\bf 7} (1956), 701--702, MR 17 \#1176. \bibitem{} D.~R. Fulkerson, {\em On perfect graph conjecture and pluperfect graph theorem}, Second Chapel Hill Conf. on Combin. Math. and its Appl., 1969, pp.~171--175. \bibitem{} D.~R. Fulkerson, {\em Blocking and anti-blocking pairs of polyhedra}, Math. Programming {\bf 1} (1971), 168--194, MR 45 \#3222. \bibitem{} D.~R. Fulkerson, {\em Anti-blocking polyhedra}, J. Combin. Theory Ser. B {\bf 12} (1972), 50--71, MR 44 \#2629. \bibitem{} D.~R. Fulkerson, {\em On the perfect graph theorem}, in Mathematical Programming (Proc. Advanced Sem., Univ. Wisconsin, Madison, Wisc., 1972), Math. Res. Center Publ., Academic Press, New York, 1973, pp.~69--76, MR 51 \#10147. \bibitem{} D.~R. Fulkerson, A.~J. Hoffman, and R.~Oppenheim, {\em On balanced matrices. {P}ivoting and extensions}, Math. Programming Stud. {\bf 1} (1974), 120--132, MR 56 \#17042. \bibitem{} H.~Galeana-S\'anchez and V.~Neuman-Lara, {\em A counterexample to a conjecture of Meyniel on kernel-perfect graphs}, Discrete Math. {\bf 41} (1982), 105-107, MR 85d:05124. \bibitem{} H.~Galeana-S\'anchez and V.~Neuman-Lara, {\em On kernels and semikernals of digraphs}, Discrete Math. {\bf 48} (1984), 67-76, MR 85i:05115. \bibitem{} H. Galeana-S\'anchez and V.~Neuman-Lara, {\em On kernel-perfect critical digraphs}, Discrete Math. {\bf 59} (1986), 257-265, MR 88b:05069. \bibitem{} H.~Galeana-S\'anchez and V.~Neuman-Lara, {\em Extending kernel perfect digraphs to kernel-perfect critical digrphs}, Discrete Math. {\bf 94} (1991), 181-187, MR 92m:05089. \bibitem{} T.~Gallai, {\em Graphen mit triangulierbaren ungeraden Vielecken}, Magyar Tud. Akad. Mat. Kutato Int. K\"ozl. {\bf 7} (1962), 3--36, MR 26 \#3039. \bibitem{} T.~Gallai, {\em Transitiv orientierbare Graphen}, Acta Math. Acad. Sci. Hungar. {\bf 18} (1967), 25--66, MR 36 \#5026. \bibitem{} F.~Gavril, {\em Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph}, SIAM J. Comput. {\bf 1} (1972), 180--187, MR 48 \#5922. \bibitem{} F.~Gavril, {\em An algorithm for testing chordality of graphs}, Inform. Process. Lett. {\bf 3} (1974), 110--112, MR 52 \#9671. \bibitem{} F.~Gavril, {\em The intersection graphs of subtrees in trees are exactly the chordal graphs}, J. Combin. Theory Ser. B {\bf 16} (1974), 47--56, MR 48 \#10868. \bibitem{} F.~Gavril, {\em Algorithms on clique separable graphs}, Discrete Math. {\bf 19} (1977), 159--165, MR 58 \#10608. \bibitem{} A.~Ghouil\`a-Houri, {\em Caract\'erisation des graphes non orient\'es dont on peut orienter les ar\^etes de mani\`ere \`a obtenir le graphe d'une relation d'ordre}, C. R. Acad. Sci. Paris {\bf 254} (1962), 1370--1371, MR 30 \#2495. \bibitem{} R.~Giles, L.~E.~Trotter,~Jr., and A.~Tucker, {\em The strong perfect graph theorem for a class of partitionable graphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 161--168, MR 86j:05061. \bibitem{} P.~C. Gilmore and A.~J. Hoffman, {\em A characterization of comparability graphs and of interval graphs}, Canad. J. Math. {\bf 16} (1964), 539--548, MR 31 \#87. \bibitem{} M.~C.~Golumbic, {\em Comparability graphs and a new matroid}, J. Combin. Theory Ser. B {\bf 22} (1977), 68--90, MR 55 \#112575. \bibitem{} M.~C.~Golumbic, {\em The complexity of comparability graph recognition and coloring}, Computing {\bf 18} (1977), 199--208, MR 58 \#19345. \bibitem{} M.~C.~Golumbic, {\em Algorithmic Graph Theory and Perfect Graphs}, Academic Press, New York, 1980, MR 81e:68081. \bibitem{} M.~C.~Golumbic, {\em Algorithmic aspects of perfect graphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 301--324, MR 86g:05072. \bibitem{} M.~C.~Golumbic, C.~L.~Monma, and W.~T.~Trotter, {\em Tolerance graphs}, Discrete Appl. Math. {\bf 9} (1984), 157--170, MR 86b:05063. \bibitem{} C.~Greene, {\em Some partitions associated with a partially ordered set}, J. Combin. Theory Ser. A {\bf 20} (1976), 69-79, MR 53 \#2763. \bibitem{} C.~Greene and D.~J.~Kleitman, {\em The structure of Sperner k-families}, J. Combin. Theory Ser. A {\bf 20} (1976), 41-68, MR 53 \#2695. \bibitem{} D.~Greenwell, {\em Odd cycles and perfect graphs}, in Theory and Applications of Graphs, Lecture Notes in Math. 642, Springer-Verlag, Berlin, 1978, pp.~191--193, MR 80d:05044. \bibitem{} C.~M.~Grinstead, {\em The strong perfect graph conjecture for toroidal graphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 97--101, MR 86e:05080. \bibitem{} C.~M.~Grinstead, {\em On circular critical graphs}, Discrete Math. {\bf 51} (1984), 11--24, MR 86g:05080. \bibitem{} M.~Gr\"otschel, L.~Lov\'asz, and A.~Schrijver, {\em The elipsoid method and its consequences in combinatorial optimization}, Combinatorica {\bf 1} (1981), 167--197, MR 84a:90044. \bibitem{} M.~Gr\"otschel, L.~Lov\'asz, and A.~Schrijver, {\em Polynomial algorithms for perfect graphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 325--356, MR 86g:05073. \bibitem{} M.~Gr\"otschel, L.~Lov\'asz, and A.~Schrijver, {\em Relaxations of vertex-packing}, J. Combin. Theory Ser. B {\bf 40} (1986), 330--343, MR 87h:05087. \bibitem{} M.~Gr\"{o}tschel, L.~Lov\'{a}sz, and A.~Schrijver, {\em Geometric Algorithms in Combinatorial Optimization}, Springer-Verlag, Berlin-New York, 1988, MR 89m:90135. \bibitem{} V.~A.~Gurvich, {\em Bilinear forms on labeled graphs} (in Russian), Doklady Akad. Nauk {\bf 325} (1992), 221--226. \bibitem{} V.~A.~Gurvich, {\em Fully separated and biseparated graphs} (in Russian), Doklady Akad. Nauk, to appear. \bibitem{} V.~A.~Gurvich, {\em Generalized Lov\'{a}sz inequality for perfect graphs} (in Russian), Uspekhi Mat. Nauk, to appear. \bibitem{} V.~A.~Gurvich and M.~A.~Temkin, {\em Checked perfect graphs} (in Russian), Doklady Akad. Nauk {\bf 326} (1992), 227-232. \bibitem{} V.~A.~Gurvich and M.~A.~Temkin, {\em Berge's conjecture is true for rotatable graphs} (in Russian), Doklady Akad. Nauk, to appear. \bibitem{} V.~A.~Gurvich, M.~A.~Temkin, V.~M.~Udalov, and A.~V.~Shapovalov, {\em Rotatable graphs without holes and antiholes} (in Russian), Doklady Akad. Nauk, {\bf 329} (1993). \bibitem{} V.~A.~Gurvich and V.~M.~Udalov, {\em Berge strong perfect graph conjecture holds for any graph which has less than 25 vertices}, manuscript. \bibitem{} V.~A.~Gurvich and V.~M.~Udalov, {\em Rotatable perfect graphs}, manuscript. \bibitem{} A.~Gy\'arf\'as, {\em Problems from the world surrounding perfect graphs}, Zastos. Mat. {\bf 19} (1987), 413--431, MR 88a:05066. \bibitem{} W.~Haemers, {\em On some problems of {L}ov\'asz concerning the {S}hannon capacity of a graph}, IEEE Trans Inform. Theory {\bf IT-25} (1979), 231--232, MR 80g:94040. \bibitem{} A.~Hajnal and J.~Sur\'anyi, {\em \"{U}ber die Aufl\"osung von Graphen in vollst\"andige Teilgraphen}, Ann. Univ. Sci. Budapest. E\"otv\"os. Sect. Math. {\bf 1} (1958), 113--121, MR 21 \#1944. \bibitem{} P.~L.~Hammer and F.~Maffray, {\em Preperfect graphs}, Combinatorica 1993, to appear. \bibitem{} F.~Harary and C.~Holzmann, {\em Line graphs of bipartite graphs}, Rev. Soc. Mat. Chile {\bf 1} (1974), 19--22. \bibitem{} R.~B.~Hayward, {\em Recognizing $P_3$-structure}, Report No. 90625-OR, Forschungsinstitut f\'ur Diskrete Mathematik, Universit\"at Bonn, January 1990. \bibitem{} R.~B. Hayward, {\em Weakly triangulated graphs}, J. Combin. Theory Ser. B {\bf 39} (1985), 200--208, MR 87h:05171. \bibitem{} R.~B.~Hayward, {\em Murky graphs are perfect}, J. Combin. Theory Ser. B {\bf 49} (1990), 220--235, MR 91f:05053. \bibitem{} R.~B. Hayward, C.~Ho\`{a}ng, and F.~Maffray, {\em Optimizing weakly triangulated graphs}, Graphs Combin. {\bf 5} (1989), 339--349, MR 91c:68051a. \bibitem{} R.~B.~Hayward, W.~J.~Lenhart, {\em On the $P_4$-structure of perfect graphs {I}{V}. Partner graphs}, J. Combin. Theory Ser. B {\bf 48} (1990), 135--139, MR 91i:05056. \bibitem{} S.~T. Hedetniemi, {\em Graphs of (0,1)-matrices}, in Recent Trends in Graph Theory (Proc. Conf., New York, 1970), Lecture Notes in Mathematics {\bf 186} (1971), 157--171, MR 43 \#6120. \bibitem{} A.~Hertz, {\em Bipartable graphs}, J. Combin. Theory Ser. B {\bf 45} (1988), 1--12, MR 89i:05116. \bibitem{} A.~Hertz, {\em Slim graphs}, Graphs Combin. {\bf 5} (1989), 149--157, MR 90f:05060. \bibitem{} A.~Hertz, {\em Skeletal graphs -- a new class of perfect graphs}, Discrete Math. {\bf 78} (1989), 291--296, MR 90i:05079. \bibitem{} A.~Hertz, {\em Slender graphs}, J. Combin. Theory Ser. B {\bf 47} (1989), 231--236, MR 91a:05078. \bibitem{} A.~Hertz, {\em A fast algorithm for colouring a {M}eyniel graph}, J. Combin. Theory Ser. B {\bf 50} (1990), 231--240, MR 91i:05111. \bibitem{} A.~Hertz and D.~de~Werra, {\em Perfectly orderable graphs are quasi-parity graphs: a short proof}, Discrete Math. {\bf 68} (1988), 111--113, MR 88m:05067. \bibitem{} C.~Ho\`{a}ng, {\em On a conjecture of {M}eyniel}, J. Combin. Theory Ser. B {\bf 42} (1987), 302--312, MR 88e:05040. \bibitem{} C.~T.~Ho\`{a}ng, {\em On the $P_4$-structure of perfect graphs {I}{I}. {O}dd decompositions}, J. Combin. Theory Ser. B {\bf 39} (1985), 220--232, MR 87c:05056b. \bibitem{} C.~T.~Ho\`{a}ng, {\em Alternating orientation and alternating colouration of perfect graphs}, J. Combin. Theory Ser. B {\bf 42} (1987), 264--273, MR 88i:05082. \bibitem{} C.~T.~Ho\`ang, {\em On the sibling-structure of perfect graphs}, J. Combin. Theory Ser. B {\bf 49} (1990), 282--286, MR 91h:05054. \bibitem{} C.~T.~Ho\`ang, {\em On the two-edge colourings of perfect graphs}, J. Graph Theory, to appear. \bibitem{} C.~T.~Ho\`{a}ng and N.~Khouzam, {\em On brittle graphs}, J. Graph Theory {\bf 12} (1988), 391-404, MR 90b:05110. \bibitem{} C.~T.~Ho\`ang and F.~Maffray, {\em Opposition graphs are strict quasi-parity graphs}, Graphs Combin. {\bf 5} (1989), 83-85, MR 89m:05097. \bibitem{} C.~T.~Ho\`ang and F.~Maffray, {\em On slim graphs, even pairs, and star-cutsets}, Discrete Math. {\bf 105} (1992), 93-102. \bibitem{} C.~T.~Ho\`ang, F.~Maffray, S.~Olariu, and M.~Preissmann, {\em A charming class of perfectly orderable graphs}, Discrete Math. {\bf 102} (1992), 67-74, MR 93b:05140. \bibitem{} C.~T.~Ho\`ang, F.~Maffray, and M.~Preissmann, {\em New properties of perfectly orderable graphs and strongly perfect graphs}, Discrete Math. {\bf 98} (1991), 161--174, MR 92m:05082. \bibitem{} C.~T.~Ho\`ang and N.~V.~R.~Mahadev, {\em A note on perfect orders}, Discrete Math. {\bf 74} (1989), 77--84, MR 90d:05098. \bibitem{} C.~T.~Ho\`{a}ng and B.~A. Reed, {\em $P_4$-comparability graphs}, Discrete Math. {\bf 4} (1989), 173--200, MR 89m:05098. \bibitem{} C.~T.~Ho\`{a}ng and B.~A. Reed, {\em Some classes of perfectly orderable graphs}, J. Graph Theory {\bf 13} (1989), 445--463, MR 90f:05117. \bibitem{} S.~Hougardy, {\em Counterexamples to three conjectures concerning perfect graphs}, Discrete Math., to appear. \bibitem{} A.~J.~Hoffman, M.~Sakarovich, and A.~Kolen, {\em Totally balanced and greedy matrices}, SIAM J. Algebraic Discrete Methods {\bf 6} (1985), 721--730, MR 86j:53011. \bibitem{} W.-L.~Hsu, {\em Coloring planar perfect graphs by decomposition}, Combinatorica {\bf 6} (1986), 381--385, MR 86b:05055. \bibitem{} W.-L. Hsu, {\em Decomposition of perfect graphs}, J. Combin. Theory Ser. B {\bf 43} (1987), 70--94, MR 88f:05045. \bibitem{} W.-L.~Hsu, {\em The perfect graph conjecture on special graphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 103--114, MR 86m:05043. \bibitem{} W.-L.~Hsu, {\em Recognizing planar perfect graphs}, J.~Assoc.~Comput.~Mach. {\bf 34} (1987), 255--258, MR 88j:68145. \bibitem{} W.-L.~Hsu, {\em The coloring and maximum independent set problems on planar perfect graphs}, J.~Assoc.~Comput.~Mach. {\bf 35} (1988), 535-563, MR 89m:68049. \bibitem{} W.-L.~Hsu, {\em How to color claw-free perfect graphs?} Ann. Discrete Math. {\bf 11} (1988), 189--197, MR 83h:05037. \bibitem{} W.-L.~Hsu and G.~L.~Nemhauser, {\em A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs}, Discrete Math. {\bf 38} (1982), 65--71, MR 84g:68051. \bibitem{} W.-L.~Hsu and G.~L.~Nemhauser, {\em Algorithms for maximum weighted cliques, minimum weighted clique covers and minimum colorings of claw-free perfect graphs}, in Topics on Perfect Graphs. Math. Stud. 88, (C. Berge and V. Chv\'atal, eds.), 1984, pp. 357--369, MR 87f:05091. \bibitem{} W.-L.~Hsu and G.~L.~Nemhauser, {\em Algorithms for minimum covering by cliques and maximum cliques on claw-free perfect graphs}, Discrete Math. {\bf 37} (1984), 181--191, MR 84i:05066. \bibitem{} M.~Hujter and Zs.~Tuza, {\em Precoloring extension III. Classes of perfect graphs}, to appear. \bibitem{} B.~Jamison and S.~Olariu, {\em On a unique tree representation of $P_4$ -extendible graphs}, Discrete Appl. Math. {\bf 34} (1991), 151-164, MR 92k:05103. \bibitem{} B.~Jamison and S.~Olariu, {\em A tree representation of $P_4$ - sparse graphs}, Discrete Appl. Math. {\bf 35}(1992), 115-129, MR 92j:05051. \bibitem{} J.~L.~Jolivet, {\em Graphes parfaits pour une propri\'et\'e {P}}, in Colloque sur la Th\'eorie des Graphes (Paris, 1974). Cahiers Centre \'Etudes Recherche Op\'er. 17 {\bf 2-3-4} (1975), 253--256, MR 53 \#7841. \bibitem{} I.~A.~Karapetian, {\em Critical and essential edges in perfect graphs} (in Russian with an Armenian summary), Akad. Nauk Armjan. SSR Dokl. {\bf 63} (1976), 65--70. \bibitem{} I.~A. Karapetian and S.~E. Markosian , {\em On perfect graphs} (in Russian with an Armenian summary), Akad. Nauk Armjan. SSR Dokl. {\bf 63} (1976), 292--296, MR 56 \#8427. \bibitem{} A.~K.~ Kelmans, {\em A minimal imperfect graph distinct from an odd cycle and from the complement to an odd cycle has no vertex of degree six or less}, XX. Internationales Wissenschaftliches Kolloquium Technische Hochschule Ilmenau -- 1978. \bibitem{} A.~K.~ Kelmans, {\em The strong perfect graph conjecture for a certain class of graphs}, XXVII. Internationales Wissenschaftliches Kolloquium Technische Hochschule Ilmenau -- 1982. \bibitem{} T.~King and G.~L.~Nemhauser, {\em Some inequalities on the chromatic number of a graph}, Discrete Math. {\bf 10} (1974), 117--121, MR 50 \#1953. \bibitem{} J.~K\"orner, {\em Coding of an information source having ambiguous alphabet and the entropy of graphs}, in Transactions of the Sixth Prague Conference on Information Theory, etc., Academia, Prague, 1973, pp.~411--425, MR 50 \#6644. \bibitem{} J.~K\"orner, {\em An extension of the class of perfect graphs}, Studia Sci. Math. Hung. {\bf 8} (1973), 405--409, MR 58 \#5402. \bibitem{} J.~K\"orner, G.~Simonyi, and Zs.~Tuza, {\em Perfect couples of graphs}, Combinatorica {\bf 12} (1992), 179-192. \bibitem{} M.~J. Krol, {\em The chromatic number of some 2-connected graphs}, in Recent Advances in Graph Theory (Proc. Second Czechoslovak Sympos., Prague, 1974), Academia, Prague, 1975, pp.~335--340, MR 53 \#5354. \bibitem{} C.~W.~H. Lam, S.~Swiercz, L.~Thiel, and E.~Regener, {\em A computer search for ($\alpha$, $\omega$)-graphs}, Proc. Ninth Manitoba Conf. Num. Math. Comp., Congressus Numerantium 27, 1979, pp.~285--289, MR 82b:05002. \bibitem{} J.~Lehel, {\em A chracterization of totally balanced hypergraphs}, Discrete Math. {\bf 37} (1985), 49-57, MR 87f:05123. \bibitem{} J.~Lehel and Zs.~Tuza, {\em Neighborhood perfect graphs}, Discrete Math. {\bf 61} (1986), 93--101, MR 87j:05128. \bibitem{} L.~Lov\'asz, {\em Normal hypergraphs and the perfect graph conjecture}, Discrete Math. {\bf 2} (1972), 253--267, MR 46 \#1626. \bibitem{} L.~Lov\'asz, {\em A characterization of perfect graphs}, J. Combin. Theory Ser. B {\bf 13} (1972), 95--98, MR 46 \#8885. \bibitem{} L.~Lov\'asz, {\em Minimax theorems for hypergraphs}, in Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972: dedicated to Arnold Ross), Lecture Notes in Math. {\bf 411} (1974), 111--126, MR 51 \#10648. \bibitem{} L.~Lov\'asz, {\em On the {S}hannon capacity of a graph}, IEEE Trans. Inform. Theory {\bf IT-25} (1979), 1--7, MR 81g:05095. \bibitem{} L.~Lov\'asz, {\em Perfect graphs}, in More Selected Topics on Graph Theory (L.~M.~Beineke and R.~L.~Wilson, eds.), Academic Press, London-New York, 1983, pp.~55--87, MR 86h:05053. \bibitem{} L.~Lov\'asz, {\em Normal hypergraphs and the weak perfect graph conjecture}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 29--42, MR 86g:05068. \bibitem{} L.~Lov\'asz, {\em Stable sets and polynomials}, Discrete Math. (1992), to appear. \bibitem{} L.~Lov\'asz and A.~Schrijver, {\em Matrix cones, projection representations, and stable set polyhedra}, in Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science I, 1989, pp.~1--17, MR 92c:52016. \bibitem{} L.~Lov\'asz and A.~Schrijver, {\em Cones of matrices and set-functions and 0-1 optimization}, SIAM J. Optim. {\bf 1} (1990), 166--190, MR 92b:05072. \bibitem{} A.~Lubiw, {\em Doubly lexical orderings of matrices}, SIAM J. Comput. {\bf 16} (1987), 854--879, MR 88m:68051. \bibitem{} A.~Lubiw, {\em Short-chorded and perfect graphs}, J. Combin. Theory Ser. B {\bf 51} (1991), 24--43, MR 92a:05095. \bibitem{} F.~Maffray, {\em On kernels in i-triangulated graphs}, Discrete Math. {\bf 61} (1986), 247--251, MR 87i:05098. \bibitem{} F.~Maffray, {\em Kernels in perfect line-graphs}, J. Combin. Theory Ser. B. {\bf 55} (1992), 1--8. \bibitem{} F.~Maffray, {\em Antitwins in partitionable graphs}, Discrete Math. {\bf 112} (1993), 275--278. \bibitem{} S.~E. Markosian, {\em Perfect and critical graphs} (in Russian with an Armenian summary), Akad. Nauk Armjan. SSR Dokl. {\bf 60} (1976), 218--223, MR 53 \#10659. \bibitem{} S.~E. Markosian, {\em On a conjecture of Berge} (in Russian), Prikl. Mat. {\bf 1} (1981), 41--46. \bibitem{} A.~S.~Markosian, {\em A critical imperfect graph containing an incomplete component} (in Russian), Uchen. Zap. {\bf 1} (1985), 33--37. \bibitem{} S.~E.~Markosian, G.~S.~Gasparian, and A.~S.~Markosian, {\em On a conjecture of {B}erge}, J. Combin. Theory Ser. B {\bf 56} (1992), 97--107. \bibitem{} S.~E. Markosian and I.~A. Karapetian, {\em On perfect graphs} (in Russian with an Armenian summary), Akad. Nauk Armjan. SSR Dokl. {\bf 63} (1976), 292--296, MR 56 \#8427. \bibitem{} S.~E. Markosian and I.~A. Karapetian, {\em On critical imperfect graphs} (in Russian), Prikl. Mat. {\bf 3} (1984), 52-60. \bibitem{} K.~Marton, {\em On the {S}hannon capacity of probabilistic graphs}, J. Combin. Theory Ser. B {\bf 57} (1993), 183-195. \bibitem{} H.~Meyniel, {\em On the perfect graph conjecture}, Discrete Math. {\bf 16} (1976), 339--342, MR 55 \#12568. \bibitem{} H.~Meyniel, {\em The graphs whose odd cycles have at least two chords}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 115--120, MR 87d:05080. \bibitem{} H.~Meyniel, {\em A new property of critical imperfect graphs and some consequences}, European J. Combin. {\bf 8} (1987), 313--316, MR 88k:05161. \bibitem{} M.~Middendorf and F.~Pfeiffer, {\em On the complexity of recognizing perfectly orderable graphs}, Discrete Math. {\bf 80} (1990), 327--333, MR 91b:68038. \bibitem{} R.~M\"ohring, {\em Algorithmic aspects of comparability graphs and interval graphs}, in Graphs and Order (I. Rival, ed.), Reidel, Dordrecht-Boston, 1985, 41-101, MR 87d:05142. \bibitem{} R.~M\"ohring and H.~Buer, {\em A fast algorithm for the decomposition of graphs and posets}, Math. Oper. Res. {\bf 8} (1983), MR 84j:05083. \bibitem{} C.~L. Monma and L.~E.~Trotter,~Jr., {\em On perfect graphs and polyhedra with (0,1)-valued extreme points}, Math. Programming {\bf 17} (1979), 239--242, MR 80i:90070. \bibitem{} S.~Olariu, {\em On the strong perfect graph conjecture}, J. Graph Theory {\bf 12} (1988), 169--176, MR 89b:05088. \bibitem{} S.~Olariu, {\em All variations on perfectly orderable graphs}, J. Combin. Theory Ser. B {\bf 45} (1988), 150-159, MR 89i:05120. \bibitem{} S.~Olariu, {\em Coersion classes in unbreakable graphs}, Ars Combin. {\bf 25} (1988), 153-180, MR 89d:05152. \bibitem{} S.~Olariu, {\em A decomposition for strongly perfect graphs}, J. Graph Theory {\bf 13} (1989), 301-311, MR 90d:05101. \bibitem{} S.~Olariu, {\em A generalization of Chv\'atal's star-cutset lemma}, Inform. Process. Lett. {\bf 33} (1989/90), 301-303, MR 91a:05082. \bibitem{} S.~Olariu, {\em Wings and perfect graphs}, Discrete Math. {\bf 80} (1990), 281-296, MR 91e:05032. \bibitem{} S.~Olariu, {\em No antitwins in minimal imperfect graphs}, J. Combin. Theory Ser. B {\bf 45} (1988), 255-257, MR 89g:05050. \bibitem{} S.~Olariu, {\em On the structure of unbreakable graphs}, J. Graph Theory {\bf 15} (1991), 349-373, MR 91a:05082. \bibitem{} E.~Olaru, {\em \"{U}ber die \"{U}berdeckung von {G}raphen mit {C}liquen}, Wiss. Z. Techn. Hochsch. Ilmenau {\bf 15} (1969), Heft 4/5, 115--121, MR 43 \#3162. \bibitem{} E.~Olaru, {\em Beitr\"{a}ge zur {T}heorie der perfekten {G}raphen} (English and Russian summaries), Elektron. Informationsverarbeit. Kybernetik {\bf 8} (1972), 147-172, MR 47 \#8338. \bibitem{} E.~Olaru, {\em \"{U}ber kritisch imperfekte {G}raphen und die starke {V}ermutung der perfekten {G}raphen}, Theorie der Graphen und Netzwerke XVIII, Int. Wiss. Koll. TH Ilmenau 1973, 19-22. \bibitem{} E.~Olaru, {\em \"{U}ber perfekte und kritisch imperfekte {G}raphen} ({R}omanian summary), An. Sti. Univ. ``Al. I. Cuza'' Iasi Sect. I a Mat. (N.S.) {\bf 19} (1973), 477--486, MR 54 \#5053. \bibitem{} E.~Olaru, {\em Zur {C}harakterisierung perfekten {G}raphen} ({E}nglish and {R}ussian summaries), Electron. Informationsverarbeit. Kybernetik {\bf 9} (1973), 543--548, MR 51 \#10167. \bibitem{} E.~Olaru, {\em On the strongly perfect and the minimal strongly imperfect graphs}, An. Univ. Galati Metal. {\bf 5(10)} (1987), 5-9, MR 89i:05120. \bibitem{} E.~Olaru, {\em Zur Theorie der perfekten Graphen}, J. Combin. Theory Ser. B {\bf 23} (1977), 94-105, MR 58 \#5411. \bibitem{} E.~Olaru and E.~M\^{a}ndrescu, {\em On stable transversals and strong perfectness of graph-join}, An. Univ. Galati Metal. {\bf 4(9)} (1986), 21-24, MR 88i:05083a. \bibitem{} E.~Olaru and E.~M\^{a}ndrescu, {\em On stable transversals in graphs} -{\em an algebraic approach}, An. Univ. Galati Metal. {\bf 4(9)} (1986), 25-30, MR 88i:05083b. \bibitem{} E.~Olaru and E.~M\^{a}ndrescu, {\em S-strongly perfect cartesian product of graphs}, J. Graph Theory {\bf 16} (1992), 297-305. \bibitem{} E.~Olaru and H.~Sachs, {\em Contributions to a characterization of the structure of perfect graphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 121--144, MR 86e:05041. \bibitem{} M.~W.~Padberg, {\em Perfect zero-one matrices}, Math. Programming {\bf 6} (1974), 180--196, MR 49 \#4809. \bibitem{} M.~W.~Padberg, {\em Characterizations of totally unimodular, balanced and perfect matrices}, in Combinatorial Programming: Methods and Applications (B. Roy, ed.), Reidel, Dordrecht, 1975, pp. 275-284, MR 53 \#10291. \bibitem{} M.~W.~Padberg, {\em Almost integral polyhedra related to certain combinatorial optimization problems}, Linear Algebra and Appl. {\bf 15} (1976), 69--88, MR 58 \#25981. \bibitem{} M.~W. Padberg, {\em A characterization of perfect matrices}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 169--178, MR 86e:05021. \bibitem{} K.~R. Parathasarathy and G.~Ravindra, {\em The strong perfect-graph conjecture is true for ${K}_{1,3}$-free graphs}, J. Combin. Theory Ser. B {\bf 21} (1976), 212--223, MR 55 \#10308. \bibitem{} K.~R. Parathasarathy and G.~Ravindra, {\em The validity of the strong perfect-graph conjecture for (${K}_4$ - e)-free graphs}, J. Combin. Theory Ser. B {\bf 26} (1979), 98--100, MR 80m:05045. \bibitem{} M.~Preissmann, {\em A class of strongly perfect graphs}, Discrete Math. {\bf 54} (1985), 117-120, MR 86g:05038. \bibitem{} M.~Preissmann, {\em Locally perfect graphs}, J. Combin. Theory Ser. B {\bf 50} (1990), 22-40, MR 92a:05096. \bibitem{} M.~Preissmann and D.~de Werra, {\em A note on strong perfectness of graphs}, Math. Programming {\bf 31} (1985), 321-326, MR 86i:05062. \bibitem{} M.~Preissmann, D.~de Werra, and N.~V.~R.~Mahadev, {\em A note on superbrittle graphs}, Discrete Math. {\bf 61} (1986), 259-267, MR 87i:05168. \bibitem{} O.~Pretzel, {\em Another proof of {D}ilworth's decomposition theorem}, Discrete Math. {\bf 25} (1979), 91--92, MR 80d:06003. \bibitem{} H.~J.~Pr\"omel and A.~Steger, {\em Almost all Berge graphs are perfect}, Combin. Probab. Comput., to appear. \bibitem{} S.~B.~Rao and G.~Ravindra, {\em A characterization of perfect total graphs}, J. Mathematical and Physical Sci. {\bf 11} (1977), 25-26, MR 58 \#21860. \bibitem{} G.~Ravindra, {\em On {B}erge's conjecture concerning perfect graphs}, Proc. Indian Nat. Sci. Acad. {\bf 41A} (1975), 294--296, MR 58 \#27607. \bibitem{} G.~Ravindra, {\em {B}-graphs}, in Proc. Symposium on Graph Theory, Indian Statistical Institute, Calcutta, 1976, pp. 268-280, MR 80m:05095. \bibitem{} G.~Ravindra, {\em Perfectness of normal products of graphs}, Discrete Math. {\bf 20} (1978), 291-298, MR 80m:05046. \bibitem{} G.~Ravindra, {\em Strongly perfect line graphs and total graphs}, in {F}inite and {I}nfinite {S}ets (A. Hajnal, Lp. Lov\'{a}sz, and V.~T.~S\'{o}s, eds.), North-Holland, Amsterdam-Oxford-New York, 1984, pp. 621-634, MR 84f:05062. \bibitem{} G.~Ravindra, {\em Meyniel's graphs are strongly perfect}, J. Combin. Theory Ser. B {\bf 33} (1982), 187--190, MR 84f:05062. \bibitem{} G.~Ravindra, {\em Meyniel's graphs are strongly perfect}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 145--148, MR 87d:05081. \bibitem{} G.~Ravindra and D.~Basavayya, {\em Co-strongly perfect graphs}, J. Mathematical and Physical Sci. {\bf 22} (1988), 439-444. \bibitem{} G.~Ravindra and K.~R.~Parthasarathy, {\em Perfect product graphs}, Discrete Math. {\bf 20} (1977/78), 177-186, MR 58 \#10567. \bibitem{} B.~A.~Reed, {\em A semi-strong perfect graph theorem}, J. Combin. Theory Ser. B {\bf 43} (1987), 223--240, MR 88g:05059. \bibitem{} B.~A.~Reed, {\em Perfection, parity, planarity and packing paths}, Proceedings of~ IPCO I, University of \\ Waterloo Press, 1990. \bibitem{} D.~J.~Rose, {\em Triangulated graphs and the elimination process}, J. Math. Anal. Appl. {\bf 32} (1970), 597--609, MR 42 \#5840. \bibitem{} D.~J. Rose and R.~E.~Tarjan, {\em Algorithmic aspects of vertex elimination}, Proc. Seventh Annual ACM Symp. on Theory of Computing {\bf 5} (1975), 245--254, MR 56 \#7320. \bibitem{} D.~J. Rose, R.~E.~Tarjan, and G.~S.~Leuker, {\em Algorithmic aspects of vertex elimination on graphs}, SIAM J. Comput. {\bf 5} (1976), 266--283, MR 53 \#12077. \bibitem{} H.~Sachs, {\em On the {B}erge conjecture concerning perfect graphs}, in Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), Gordon and Breach, New York, 1970, pp.~377--384, MR 42 \#7549. \bibitem{} M.~Saks, {\em A class of perfect graphs associated with planar rectilinear regions}, SIAM J. Algebraic and Discrete Methods {\bf 3} (1982), 330--342, MR 84d:05079. \bibitem{} M.~Saks, {\em Some integer sequences associated with combinatorial structures}, Discrete Math. {\bf 59} (1986), 135--166, MR 87f:05017. \bibitem{} A.~Sassano, {\em Reducible cliques and the strong perfect graph conjecture}, IASI Technical Rep.~R. 257, March 1989. \bibitem{} A.~Seb\H o, {\em Forcing colorations, and the perfect graph conjecture}, in Integer Programming and Combinatorial Optimization {\bf 2} (E.~Balas, G.~Cornu\'{e}jols, and R.~Kannan, eds.), Mathematics Programming Society and Carnegie Mellon University, 1992. \bibitem{} D.~Seinsche, {\em On a property of the class of n-colorable graphs}, J. Combin. Theory Ser. B {\bf 16} (1974), 191--193, MR 49 \#2448. \bibitem{} C.~Shannon, {\em The zero error capacity of a noisy channel}, IRE Trans. Inform. Theory {\bf IT-2} (1956), 8--19. \bibitem{} L.~Sun, {\em Two classes of perfect graphs}, J. Combin. Theory Ser. B {\bf 53} (1991), 273--291. \bibitem{} L.~Sur\'anyi, {\em The covering of graphs by cliques}, Studia Sci. Math. Hungar. {\bf 3} (1968), 345--349, MR 38 \#76. \bibitem{} R.~E.~Tarjan, {\em Decomposition by clique separators}, Discrete Math. {\bf 55} (1985), 221--232, MR 87i:05134. \bibitem{} R.~E.~Tarjan and M.~Yannakakis, {\em Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs}, SIAM J. Comput. {\bf 13} (1984), 566--579, Addendum, ibid 14 (1985), 254-255, MR 86f:68017. \bibitem{} I.~Tomescu, {\em Sur le nombre des cliques maximales d'un graphe et quelques probl\`emes sur les graphes parfaits}, Rev. Roumaine Math. Pures Appl. {\bf 16} (1971), 1115--1126, MR 45 \#103. \bibitem{} L.~E.~Trotter,~Jr., {\em A class of facet producing graphs for vertex packing polyhedra}, Discrete Math. {\bf 12} (1975), 373--388, MR 53 \#2759. \bibitem{} L.~E.~Trotter,~Jr., {\em Line perfect graphs}, Math. Programming {\bf 12} (1977), 255--259, MR 56 \#15501. \bibitem{} A.~Tucker, {\em The strong perfect graph conjecture and an application to a municipal routing problem}, in Graph Theory and Applications (Proc. Conf. Western Michigan Univ., Kalamazoo, Mich. 1972), Lecture Notes in Math. {\bf 303} (1972), 297--303, MR 49 \#7181. \bibitem{} A.~Tucker, {\em Perfect graphs and an application to optimizing municipal services}, SIAM Rev. {\bf 15} (1973), 585--590, MR 48 \#3817. \bibitem{} A.~Tucker, {\em The strong perfect graph conjecture for planar graphs}, Canad. J. Math. {\bf 25} (1973), 103--114, MR 47 \#4868. \bibitem{} A.~Tucker, {\em Structure theorems for some circular-arc graphs}, Discrete Math. {\bf 7} (1974), 167--195, MR 52 \#203. \bibitem{} A.~Tucker, {\em Coloring a family of circular arcs}, SIAM J. Appl. Math. {\bf 29} (1975), 493--502, MR 55 \#10309. \bibitem{} A.~Tucker, {\em Critical perfect graphs and perfect 3-chromatic graphs}, J. Combin. Theory Ser. B {\bf 23} (1977), 143--149, MR 58 \#16369. \bibitem{} A.~Tucker, {\em On {B}erge's strong perfect graph conjecture}, Ann. N.Y. Acad. Sci. {\bf 319} (1979), 530--535, MR 81c:05041. \bibitem{} A.~Tucker, {\em Coloring graphs with stable cutsets}, J. Combin. Theory Ser. B {\bf 34} (1983), 258--267, MR 85d:05120. \bibitem{} A.~Tucker, {\em Uniquely colorable perfect graphs}, Discrete Math. {\bf 44} (1983), 187-194, MR 84k:05047. \bibitem{} A.~Tucker, {\em The validity of the perfect graph conjecture for $K_4$-free graphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 149--158, MR 86j:05067. \bibitem{} A.~Tucker, {\em Coloring perfect $(K_4-e)$-free graphs}, J. Combin. Theory Ser. B {\bf 42} (1987), 313-318, MR 88f:05047. \bibitem{} A.~Tucker, {\em A reduction procedure for coloring perfect $K_4$-free graphs}, J. Combin. Theory Ser. B {\bf 43} (1987), 151-172, MR 88k:05085. \bibitem{} Zs.~Tuza, {\em Covering all cliques of a graph}, Discrete Math. {\bf 86} (1990), 117--126, MR 91i:05092. \bibitem{} Zs.~Tuza, {\em Perfect graph decompositions}, Graphs Combin. {\bf 7} (1991), 89--93, MR 92d:05076. \bibitem{} Zs.~Tuza, {\em Perfect triangle families}, Bull. London Math. Soc., to appear. \bibitem{} H.~Tverberg, {\em On {D}ilworth's decomposition theorem for partially ordered sets}, J. Combin. Theory Ser. B {\bf 3} (1967), 305--305, MR 35 \#5366. \bibitem{} M.~Las Vergnas, {\em Sur les hypergraphes bichromatiques}, in Hypergraph Seminar, Lecture Notes in Math. {\bf 411} (1974), 102--110, MR 51 \#10150. \bibitem{} J.~R. Walter, {\em Representations of chordal graphs as subtrees of a tree}, J. Graph Theory {\bf 2} (1978), 265--267, MR 58 \#21868. \bibitem{} W.~Wessel, {\em Some color-critical equivalents of the strong perfect graph conjecture}, in Beitr\"age zur Graphentheorie und deren Anwendung (Proc. Int. Koll. ``Graphentheorie und deren Anwendungen'' (DDR) 10-16 April 1977) (Math. Ges. DDR. TH Ilmenau), 1977, pp.~300--309, MR 82h:05033. \bibitem{} S.~H.~Whitesides, {\em An algorithm for finding clique cut-sets}, Inform. Process. Lett. {\bf 12} (1981), 31--32, MR 82a:68133. \bibitem{} S.~H.~Whitesides, {\em A classification of certain graphs with minimal imperfection properties}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 207--218, MR 86i:05090. \bibitem{} S.~H.~Whitesides, {\em A method for solving certain graph recognition and optimization problems with applications to perfect graphs}, in Topics on Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.), 1984, pp. 281--298, MR 86i:05091. \bibitem{} L.~S.~Zaremba, {\em Perfect graphs and norms}, Math. Programming {\bf 51} (1991), 269-272, MR 92m:05162. \end{thebibliography} \end{document}