A bibliography on perfect graphs

PERFECT PAPERS

Created on 22 August, 2000
Last updated on 5 July, 2006

Here is a bibliography of selected papers on perfect graphs. In making the selection, I tried to include only papers that

have been published in a journal or a collection reviewed in Mathematical Reviews, or else are available on the web in an electronic form.

and

are reasonably relevant to Claude Berge's Strong Perfect Graph Conjecture or to the problem of recognizing perfect graphs in polynomial time. (For instance, I did not want to have the bibliography teeming with the numerous papers on interval graphs, even though these graphs are perfect.)

Since the 2000 Mathematics Subject Classification includes

05C17 Perfect graphs

such papers reviewed in MathSciNet after 2000 are easy to find. For this reason, I have stopped updating the bibliography. Still, I could not help including the two recently published milestones

M. Chudnovsky, N. Robertson, P.D. Seymour, and R.Thomas, The strong perfect graph theorem, Ann. Math. 164 (2006), 51--229

and

M. Chudnovsky, G. Cornuéjols, X. Liu, P.D. Seymour, and K. Vušković, Recognizing Berge Graphs, Combinatorica 25 (2005), 143--186.

Vašek Chvátal

Open problems on perfect graphs
Problems from the AIM Workshop on Perfect Graphs
(compiled by Maria Chudnovsky)
Home pages of people interested in perfect graphs
Vašek Chvátal's home page

H. L. Abbott and B. Zhou, The star chromatic number of a graph, J. Graph Theory 17 (1993), 349--360. MR 94g:05032
R. Aharoni and R. Holzman, Fractional kernels in digraphs, J. Combin. Theory Ser. B 73 (1998), 1--6. MR 99e:05058
H. Aït Haddadène and S. Gravier, On weakly diamond-free Berge graphs, Discrete Math. 159 (1996), 237--240. MR 97e:05081
H. Aït Haddadène, S. Gravier, and F. Maffray, An algorithm for coloring some perfect graphs, Discrete Math. 183 (1998), 1--16. MR 99b:05051
H. Aït Haddadène and F. Maffray, Coloring perfect degenerate graphs, Discrete Math. 163 (1997), 211--215. MR 97g:05072
J. Akiyama and V. Chvátal, Packing paths perfectly, Discrete Math. 85 (1990), 247--255. MR 92a:68114
V. A. Aksënov, The degree of perfection of a graph. (Russian) Metody Diskret. Analiz. (1984), 3--11, 108. MR 87h:05084
M. O. Albertson and D. M. Berman, Cliques, colorings, and locally perfect graphs, Proceedings of the fourteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1983), Congr. Numer. 39 (1983), 69--73. MR 85g:05074
M. O. Albertson and K. L. Collins, Duality and perfection for edges in cliques, J. Combin. Theory Ser. B 36 (1984), 298--309. MR 85k:05037
G. Alexe and E. Olaru, The strongly perfectness of normal product of t-perfect graphs, Graphs Combin. 13 (1997), 209--215. MR 98m:05064
R. P. Anstee and M. Farber, Characterizations of totally balanced matrices, J. Algorithms 5 (1984), 215--230. MR 86e:05019

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A. Yu. Babaitsev, The strong Berge conjecture for edge graphs of linear 3-colorable hypergraphs. (Russian) Dokl. Nats. Akad. Nauk Belarusi 42 (1998), 34--37, 124. MR 2000g:05060
L. Babel, A. Brandstädt, and V. B. Lê, Recognizing the P₄-structure of bipartite graphs, Discrete Appl. Math. 93 (1999), 157--168.
L. Babel, A. Brandstädt, and V. B. Lê, Recognizing the P₄-structure of claw-free graphs and a larger graph class, Discrete Math. Theor. Comput. Sci. 5 (2002), 127--146 (electronic).
L. Babel and S. Olariu, A new characterization of P₄-connected graphs, Graph-theoretic concepts in computer science (Cadenabbia, 1996), Lecture Notes in Comput. Sci. 1197, Springer, Berlin, 1997, pp. 17--30. MR 98f:05102
L. Babel and S. Olariu, On the p-connectedness of graphs---a survey, Discrete Appl. Math. 95 (1999), no. 1-3, 11--33. MR 2000g:05093
G. Bacsó, On a conjecture about uniquely colorable perfect graphs, Discrete Math. 176 (1997), 1--19. MR 98j:05066
G. Bacsó, E. Boros, V. Gurvich, F. Maffray, and M. Preissmann, On minimal imperfect graphs with circular symmetry, J. Graph Theory 29 (1998), 209--225. MR 2000h:05116
G. Bacsó and Zs. Tuza, Dominating cliques in P₅-free graphs, Period. Math. Hungar. 21 (1990), 303--308. MR 92g:05150
V. Barré, On vertex neighborhood in minimal imperfect graphs, Graph theory (Prague, 1998), Discrete Math. 233 (2001), 211--218. MR 2002a:05117
V. Barré and J.-L. Fouquet, On minimal imperfect graphs without induced P₅, Proceedings of the Third International Conference on Graphs and Optimization, GO-III (Leukerbad, 1998), Discrete Appl. Math. 94 (1999), 9--33. MR 2000e:05073
V. Barré and J.-L. Fouquet, On minimal cutsets in P₅-free minimal imperfect graphs, Graph theory (Kazimierz Dolny, 1997), Discrete Math. 236 (2001), 25--36. MR 2002a:05157
D. Basavayya and G. Ravindra, Strongly perfect line graphs of (0,1)-graphs, J. Combin. Inform. System Sci. 10 (1985), 157--160. MR 89g:05048
D. Basavayya and G. Ravindra, Strongly perfect line graphs of (0,1)-graphs, J. Math. Phys. Sci. 21 (1987), 391--398. MR 88i:05076
C. Benzaken and P. L. Hammer, Boolean techniques for matroidal decomposition of independence systems and applications to graphs, Discrete Math. 56 (1985), 7--34. MR 87e:05042
C. Benzaken, P. L. Hammer, and D. de Werra, Threshold characterization of graphs with Dilworth number two, J. Graph Theory 9 (1985), 245--267. MR 87d:05135
C. Berge, Les problèmes de coloration en théorie des graphes, Publ. Inst. Statist. Univ. Paris 9 (1960) 123--160. MR 23 #A1551
C. Berge, Färbung von Graphen, deren sämtliche bzw. deren ungeraden Kreise starr sind (Zusammenfassung), Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114.
C. Berge, Perfect graphs, in: Six Papers on Graph Theory, Research and Training School, Indian Statistical Institute, Calcutta, 1963, pp. 1--21.
C. Berge, Une application de la théorie des graphes à un problème de codage. Automata Theory (E. R. Caianiello, ed.) Academic Press, New York, 1966, pp. 25--34. MR 43 #83
C. Berge, Some classes of perfect graphs. Graph Theory and Theoretical Physics (F. Harary, ed.) Academic Press, London, 1967, pp. 155--165. MR 38 #1017
C. Berge, Some classes of perfect graphs. Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, N.C., 1967; R. C. Bose and T. A. Dowling, eds.) Univ. North Carolina Press, Chapel Hill, N.C., 1969, pp. 539--552. MR 42 #100
C. Berge, The rank of a family of sets and some applications to graph theory. Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968; W. T. Tutte, ed.), Academic Press, New York, pp. 49--57. MR 41 #5231
C. Berge, Balanced hypergraphs and some applications to graph theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971; J. N. Srivastava, ed.), North-Holland, Amsterdam, 1973, pp. 15--23. MR 51 #2970
C. Berge, Balanced matrices, Math. Programming 2 (1972), 19--31. MR 48 #142
C. Berge, Perfect graphs. Studies in graph theory, Part I (D. R. Fulkerson, ed.), Studies in Math., Vol. 11, Math. Assoc. Amer., Washington, D. C., 1975, pp. 1--22. MR 53 #10585
C. Berge, Balanced matrices and property G. Combinatorial optimization, Math. Programming Stud. (1980), 163--175. MR 82d:05080
C. Berge, Diperfect graphs. Combinatorics and graph theory (Calcutta, 1980), Lecture Notes in Math., 885, Springer, Berlin-New York, 1981, pp. 1--8. MR 84h:05053
C. Berge, Diperfect graphs, Combinatorica 2 (1982), 213--222. MR 84j:05059
C. Berge, Stochastic graphs and strongly perfect graphs---a survey, Southeast Asian Bull. Math. 7 (1983), 16--25. MR 85d:05202
C. Berge, Stochastic graphs and strongly perfect graphs: a survey. Combinatorics and applications (Calcutta, 1982), Indian Statist. Inst., Calcutta, 1984, pp.60--65. MR 87i:05162
C. Berge, Minimax theorems for normal hypergraphs and balanced hypergraphs---a survey. Topics on perfect graphs, North-Holland Math. Stud., 88,North-Holland, Amsterdam-New York, 1984, pp.3--19. MR 86i:05107
C. Berge, Diperfect graphs. Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 45--56. MR 86m:05047
C. Berge, New classes of perfect graphs. Applications of combinatorial methods in mathematical programming (Gainesville, Fla., 1985), Discrete Appl. Math. 15 (1986), 145--154. MR 87i:05085
C. Berge, Minimax relations for the partial q-colorings of a graph. Graph colouring and variations, Discrete Math. 74 (1989), 3--14. MR 90c:05080
C. Berge, The q-perfect graphs. I. The case q=2. Sets, graphs and numbers (Budapest, 1991; L. Lovász, D. Miklos, and T. Szönyi, eds.), Colloq. Math. Soc. János Bolyai, 60, North-Holland, Amsterdam, 1992, pp.67--75. MR 94d:05110
C. Berge, The q-perfect graphs. II.Combinatorics 92 (Catania, 1992), Matematiche (Catania) 47 (1992), 205--211 (1993). MR 95h:05126
C. Berge, The q-perfect graphs. Graph theory, combinatorics, and algorithms, Vol. 1, 2 (Kalamazoo, MI, 1992), Wiley-Intersci. Publ., Wiley, New York, 1995, pp.47--62. MR 97c:05060
C. Berge, The history of the perfect graphs, Southeast Asian Bull. Math. 20 (1996), 5--10. MR 97a:05007
C. Berge, Motivations and history of some of my conjectures. Graphs and combinatorics (Marseille, 1995). Discrete Math. 165/166 (1997), 61--70. MR 98a:05091
C. Berge, C. C. Chen, V. Chvátal, and C. S. Seow, Combinatorial properties of polyominoes, Combinatorica 1 (1981), 217--224. MR 83b:05051
C. Berge and V. Chvátal, eds. Topics on perfect graphs. North-Holland Mathematics Studies, 88. Annals of Discrete Mathematics, 21. North-Holland Publishing Co., Amsterdam-New York, 1984. xiv+369 pp. ISBN: 0-444-86587-X MR 85k:05006
C. Berge and P. Duchet, Strongly perfect graphs. Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 57--61. MR 86g:05077
C. Berge and P. Duchet, Perfect graphs and kernels, Bull. Inst. Math. Acad. Sinica 16 (1988), 263--274. MR 91a:05048
C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs. Applications of discrete mathematics (Clemson, SC, 1986), SIAM, Philadelphia, PA, 1988, pp. 200--204. MR 89i:05124
C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs, Discrete Math. 86 (1990), 27--31. MR 91m:05091
C. Berge and M. Las Vergnas, Sur un théorème du type König pour hypergraphes, Ann. New York Acad. Sci. 175 (1970) 32--40. MR 42 #1690
C. Berge and J. L. Ramírez Alfonsín, Origins and genesis, in: Perfect Graphs (J.L. Ramírez Alfonsín and B.A. Reed, eds.), Wiley, 2001, pp. 1--12. MR 1 861 355
M. E. Bertschi, Perfectly contractile graphs, J. Combin. Theory Ser. B 50 (1990), 222--230. MR 91j:05042
M. E. Bertschi and B. A. Reed, Erratum: "A note on even pairs" [Discrete Math. {65} (1987), 317--318; MR 88f:05066] by Reed, Discrete Math. 71 (1988), 187. MR 89e:05123
H. Bielak, Generalized neighbourhoods and perfectly orderable graphs. Graphs, hypergraphs and matroids, III (Kalsk, 1988), Higher College Engrg., Zielona Góra, 1989, pp. 7--16. MR 91j:05086
D. Bienstock, On the complexity of testing for odd holes and induced odd paths, Discrete Math. 90 (1991), 85--92. MR 92m:68040a Corrigendum: Discrete Math. 102 (1992), 109. MR 92m:68040b
R. E. Bixby, A composition for perfect graphs. Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 221--224. MR 86f:05105
R. G. Bland, H. C. Huang, and L. E. Trotter, Jr., Graphical properties related to minimal imperfection, Discrete Math. 27 (1979), 11--22. MR 80g:05034
R. G. Bland, H. C. Huang, and L. E. Trotter, Jr., Graphical properties related to minimal imperfection. Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 181--192. MR 86e:05075
M. Blidia, A parity digraph has a kernel, Combinatorica 6 (1986), 23--27. MR 88e:05046
M. Blidia, P. Duchet, , and F. Maffray, On kernels in perfect graphs, Combinatorica 13 (1993), 231--233. MR 94e:05099
M. Blidia, P. Duchet, and F. Maffray, On the orientation of Meyniel graphs, J. Graph Theory 18 (1994), 705--711. MR 95j:05102
M. Blidia, P. Duchet, and F. Maffray, Les graphes faiblement triangulés sans P₅ sont C-parfaits, Maghreb Math. Rev. 5 (1996), 13--24.MR 2001h:05043
M. Blidia and K. Engel, Perfectly orderable graphs and almost all perfect graphs are kernel M-solvable, Graphs Combin. 8 (1992), 103--108. MR 93h:05131
E. Boros and O. Cepek, On perfect 0,±1 matrices. Graphs and combinatorics (Marseille, 1995), Discrete Math. 165/166 (1997), pp. 81--100. MR 98g:05028
E. Boros and V. Gurvich, Perfect graphs are kernel solvable, Discrete Math. 159 (1996), 35--55. MR 97h:05063
E. Boros and V. Gurvich, Stable effectivity functions and perfect graphs, Math. Social Sci. 39 (2000), 175--194. MR 2001b:91023
E. Boros, V. Gurvich, and S. Hougardy, Recursive Generation of Partitionable Graphs (electronic), Rutcor Research Report RRR10-99.
A. Brandstädt and V. B. Lê, Recognizing the P₄-structure of block graphs, Discrete Appl. Math. 99 (2000), 349--366.
A. Brandstädt, V. B. Lê, and S. Olariu, Linear-Time Recognition of the P₄-structure of Trees, Rutcor Research Report RRR 19-96, Rutgers University, 1996.
A. Brandstädt, V. B. Lê, and J. Spinrad, Graph Classes: A Survey, SIAM, Philadelphia, 1999. xii + 304 pp. ISBN: 0-89871-432-X
M. A. Buckingham and M. C. Golumbic, Recent results on the strong perfect graph conjecture, Convexity and graph theory (Jerusalem, 1981), 75--82, North-Holland Math. Stud., 87, North-Holland, Amsterdam-New York, 1984. MR 86h:05048
M. A. Buckingham and M. C. Golumbic, Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture, Discrete Math. 44 (1983), 45--54. MR 84g:05119
P. Buneman, A characterisation of rigid circuit graphs, Discrete Math. 9 (1974), 205--212. MR 50 #9686
M. Burlet and J. Fonlupt, Polyhedral consequences of the amalgam operation. Graphs and combinatorics (Lyon, 1987; Montreal, PQ, 1988). Discrete Math. 130 (1994), pp. 39--55. MR 95i:05089
M. Burlet and J. Fonlupt, Polynomial algorithm to recognize a Meyniel graph, Progress in combinatorial optimization (Waterloo, Ont., 1982), 69--99, Academic Press, Toronto, Ont., 1984. MR 86g:05078
M. Burlet and J. Fonlupt, Polynomial algorithm to recognize a Meyniel graph, Topics on perfect graphs, 225--252, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984. MR 86h:05090
M. Burlet and J.-P. Uhry, Parity graphs, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 253--277. MR 86i:05116
M. Burlet and J.-P. Uhry, Parity graphs, Bonn Workshop on Combinatorial Optimization (Bonn, 1980), Ann. Discrete Math., 16, North-Holland, Amsterdam-New York, 1982, pp. 1--26. MR 84j:05067

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
L. Cai and D. G. Corneil, A generalization of perfect graphs---i-perfect graphs, J. Graph Theory, 23 (1996), 87--103. MR 97f:05063
K. Cameron, A min-max relation for the partial q-colourings of a graph. II. Box perfection, Graph colouring and variations, Discrete Math. 74 (1989), 15--27. MR 90c:05081
K. Cameron and J. Edmonds, Lambda composition, J. Graph Theory 26 (1997), 9--16. MR 99c:05149
K. Cameron, J. Edmonds, and L. Lovász, A note on perfect graphs, Period. Math. Hungar. 17 (1986), 173--175. MR 87i:05093
D. Cao and G. L. Nemhauser, Polyhedral characterizations and perfection of line graphs, Discrete Appl. Math. 81 (1998), 141--154. MR 99h:05099
O. M. Carducci, The strong perfect graph conjecture holds for diamonded odd cycle-free graphs, Discrete Math. 110 (1992), 17--34. MR 94b:05075
C. Champetier, Kernels in some orientations of comparability graphs, J. Combin. Theory Ser. B 47 (1989), 111--113. MR 90g:05090
G. J. Chang, M. Farber, and Zs. Tuza, Algorithmic aspects of neighborhood numbers, SIAM J. Discrete Math. 6 (1993), 24--29. MR 94b:05144
G. J. Chang and G. L. Nemhauser, Covering, packing and generalized perfection, SIAM J. Algebraic Discrete Methods 6 (1985), 109--132. MR 86h:05085
F. Cheah and D. G. Corneil, On the structure of trapezoid graphs, Discrete Appl. Math. 66 (1996), 109--133. MR 97f:05158
K. B. Chilakamarri and P. Hamburger, On a class of kernel-perfect and kernel-perfect-critical graphs, Discrete Math. 118 (1993), 253--257. MR 94b:05156
S. A. Choudum, K. R. Parthasarathy, and G. Ravindra, Line-clique cover number of a graph, Proc. Indian Nat. Sci. Acad. Part A 41 (1975), 289--293. MR 58 #27638
V. Chvátal, On certain polytopes associated with graphs, J. Combinatorial Theory Ser. B 18 (1975), 138--154. MR 51 #7949
V. Chvátal, On the strong perfect graph conjecture, J. Combinatorial Theory Ser. B 20 (1976), 139--141. MR 54 #129
V. Chvátal, A semistrong perfect graph conjecture. Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 279--280. MR 86j:05119
V. Chvátal, An equivalent version of the strong perfect graph conjecture. Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 193--195. MR 86j:05058
V. Chvátal, Notes on perfect graphs, Progress in combinatorial optimization (Waterloo, Ont., 1982), Academic Press, Toronto, Ont., 1984, pp. 107--115. MR 86h:05091
V. Chvátal, Perfectly ordered graphs. Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 63--65. MR 86j:05059
V. Chvátal. Recent results on perfect graphs, International Symposium on Circuits and Systems Proceedings, The IEEE Circuits and Systems Society, 1985, pp. 1183--1186.
V. Chvátal, Star-cutsets and perfect graphs, J. Combin. Theory Ser. B 39 (1985), 189--199. MR 87a:05066
V. Chvátal, On the P₄-structure of perfect graphs. III. Partner decompositions, J. Combin. Theory Ser. B 43 (1987), 349--353. MR 89a:05062
V. Chvátal, Perfect graphs, Surveys in combinatorics 1987 (New Cross, 1987), London Math. Soc. Lecture Note Ser., 123, Cambridge Univ. Press, Cambridge-New York, 1987, pp. 43--51. MR 88k:05079
V. Chvátal, Which line-graphs are perfectly orderable? J. Graph Theory 14 (1990), 555--558. MR 92a:05105
V. Chvátal, Which claw-free graphs are perfectly orderable? Discrete Appl. Math. 44 (1993), 39--63. MR 94e:05208
V. Chvátal and C. Ebenegger, A note on line digraphs and the directed max-cut problem. First International Colloquium on Pseudo-Boolean Optimization and Related Topics (Chexbres, 1987), Discrete Appl. Math. 29 (1990), 165--170. MR 91i:05059
V. Chvátal, J. Fonlupt, L. Sun, and A. Zemirline, Recognizing dart-free perfect graphs. Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), ACM, New York, 2000, pp. 50--53, CMP 1 754 840
V. Chvátal, R. L. Graham, A. F. Perold, and S. H. Whitesides, Combinatorial designs related to the strong perfect graph conjecture, Discrete Math. 26 (1979), 83--92. MR 81b:05044
V. Chvátal, R. L. Graham, A. F. Perold, and S. H. Whitesides, Combinatorial designs related to the perfect graph conjecture. Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 197--206. MR 87f:05067
V. Chvátal and C. T. Hoàng, On the P₄-structure of perfect graphs. I. Even decompositions, J. Combin. Theory Ser. B 39 (1985), 209--219. MR 87c:05056a
V. Chvátal, C. T. Hoàng, N. V. R. Mahadev, and D. de Werra, Four classes of perfectly orderable graphs, J. Graph Theory 11 (1987), 481--495. MR 88i:05079
V. Chvátal, W. J. Lenhart, and N.Sbihi, Two-colourings that decompose perfect graphs, J. Combin. Theory Ser. B 49 (1990), 1--9. MR 91f:05051
V. Chvátal and N.Sbihi, Bull-free Berge graphs are perfect, Graphs Combin. 3 (1987), 127--139. MR 89a:05063
V. Chvátal and N. Sbihi, Recognizing claw-free perfect graphs, J. Combin. Theory Ser. B 44 (1988), 154--176. MR 89e:05165
M. Cochand and D. de Werra, Generalized neighbourhoods and a class of perfectly orderable graphs, Applications of combinatorial methods in mathematical programming (Gainesville, Fla., 1985), Discrete Appl. Math. 15 (1986), 213--220. MR 88g:05111
M. Conforti, (K₄-e)-free perfect graphs and star cutsets, Combinatorial optimization (Como, 1986), Lecture Notes in Math., 1403, Springer, Berlin-New York, 1989, pp. 236--253. MR 91c:05078
M. Conforti, D. G. Corneil, and A. R. Mahjoub, K_i-covers. II. K_i-perfect graphs, J. Graph Theory 11 (1987), 569--584. MR 89i:05210
M. Conforti and G. Cornuéjols, Balanced 0,±1-matrices, bicoloring and total dual integrality, Math. Programming 71 (1995), Ser. A, 249--258. MR 97a:90103
M. Conforti, G. Cornuéjols, and C. De Francesco, Perfect 0,±1 matrices, Linear Algebra Appl. 253 (1997), 299--309. MR 97m:15034
M. Conforti, G. Cornuéjols, G.Gasparyan, and K. Vušković, Perfect Graphs, Partitionable Graphs and Cutsets Combinatorica 22 (2002), no. 1, 19--33. MR 1 884 056
M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković, Recognizing balanced 0,±1 matrices, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, VA, 1994), ACM, New York, 1994, pp. 103--111. MR 95e:05022
M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković, A mickey-mouse decomposition theorem, Integer programming and combinatorial optimization (Copenhagen, 1995), Lecture Notes in Comput. Sci., 920, Springer, Berlin, 1995, pp. 321--328. MR 96i:05139
M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković, Universally signable graphs, Combinatorica 17 (1997), 67--77. MR 98g:05134
M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković, Perfect, ideal and balanced matrices, . European J. Oper. Res. 133 (2001), 455--461. MR 2002e:05062
M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković, Even and odd holes in cap-free graphs, J. Graph Theory 30 (1999), 289--308. MR 99m:05155
M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković, Balanced 0+-1 Matrices Part I: Decomposition, J. Combin. Theory Ser. B. 81 (2001), 243--274.
M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković, Balanced 0+-1 Matrices Part II: Algorithm, in J. Combin. Theory Ser. B. 81 (2001), 275--306.
M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković, Even-Hole-Free Graphs Part I: Decomposition Theorem J. Graph Theory 39 (2002), 6--49.
M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković, Even-Hole-Free Graphs Part II: Recognition Algorithm J. Graph Theory 40 (2002), 238--266.
M. Conforti, G. Cornuéjols, and M. R. Rao, Decomposition of wheel-and-parachute-free balanced bipartite graphs, Partitioning and decomposition in combinatorial optimization, Discrete Appl. Math. 62 (1995), 103--117. MR 96m:05121
M. Conforti, G. Cornuéjols, and M. R. Rao, Decomposition of balanced matrices, J. Combin. Theory Ser. B 77 (1999), 292--406. MR 2001d:05126
M. Conforti, G. Cornuéjols, and K. Truemper, From totally unimodular to balanced 0,±1 matrices: a family of integer polytopes, Math. Oper. Res. 19 (1994), 21--23. MR 96e:15023
M. Conforti, G. Cornuéjols, and K. Vušković, Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1999), 27--33. MR 99j:05119
M. Conforti and M. R. Rao, Articulation sets in linear perfect matrices. I. Forbidden configurations and star cutsets, Discrete Math. 104 (1992), 23--47. MR 93i:05058. Addendum: Discrete Math. 120 (1993), 309. CMP 1 235 924
M. Conforti and M. R. Rao, Articulation sets in linear perfect matrices. II. The wheel theorem and clique articulations, Discrete Math. 110 (1992), 81--118. MR 94b:05077
M. Conforti and M. R. Rao, Testing balancedness and perfection of linear matrices, Math. Programming 61 (1993), Ser. A, 1--18. MR 94f:05027
D. G. Corneil, Families of graphs complete for the strong perfect graph conjecture, J. Graph Theory 10 (1986), 33--40. MR 87d:05073
D. G. Corneil and J. Fonlupt, Stable set bonding in perfect graphs and parity graphs, J. Combin. Theory Ser. B 59 (1993), 1--14. MR 94f:05052
D. G. Corneil and P. A. Kamula, Extensions of permutation and interval graphs, Eighteenth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Fla., 1987), Congr. Numer. 58 (1987), 267--275. MR 89e:05076
D. G. Corneil and D. G. Kirkpatrick, Families of recursively defined perfect graphs, Proceedings of the fourteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1983), Congr. Numer. 39 (1983), pp. 237--246. MR 85k:05045
G. Cornuéjols and W. H. Cunningham, Compositions for perfect graphs, Discrete Math. 55 (1985), 245--254. MR 86j:05120
G. Cornuéjols and B. A. Reed, Complete multi-partite cutsets in minimal imperfect graphs, J. Combin. Theory Ser. B 59 (1993), 191--198. MR 95b:05072
C. Croitoru, A structural property of monsters, ROSYCS'98 (Ia\c si), An. \c Stiin\c t. Univ. Al. I. Cuza Ia\c si Inform. (N.S.) 8 (1999), 64--66 (2000). CMP 1 777 431
C. Croitoru and C. Radu, Colourings and orderings in a graph, An. \c Stiin\c t. Univ. "Al. I. Cuza" Ia\c si Inform. (N.S.) 1 (1992), 11--16. MR 94m:05076
C. Croitoru and C. Radu, Submodularity relations for the independence function of a graph, An. \c Stiin\c t. Univ. "Al. I. Cuza" Ia\c si Inform. (N.S.) 1 (1992), 3--10. MR 95a:05088
C. Croitoru and C. Radu, C-perfect graphs, An. \c Stiin\c t. Univ. Al. I. Cuza Ia\c si Inform. (N.S.) 2 (1993), 61--71. MR 96g:05114
I. Csiszár, J. Körner, L. Lovász, K. Marton, and G. Simonyi, Entropy splitting for antiblocking corners and perfect graphs, Combinatorica 10 (1990), 27--40. MR 92a:05093

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
I. Dagan, M.C. Golumbic, and R. Y. Pinter, Trapezoid graphs and their coloring, Discrete Appl. Math. 21 (1988), 35--46. MR 89i:05115
R. C. Dalang, L. E. Trotter, Jr., and D. de Werra, On randomized stopping points and perfect graphs, J. Combin. Theory Ser. B 45 (1988), 320--344. MR 90b:05120
P. Damaschke, Forbidden ordered subgraphs, Topics in combinatorics and graph theory (Oberwolfach, 1990), Physica, Heidelberg, 1990, pp. 219--229. MR 92d:05132
C. De Simone and A. Galluccio, New classes of Berge perfect graphs, Discrete Math. 131 (1994), 67--79. MR 95f:05040
C. De Simone and J. Körner, On the odd cycles of normal graphs, Proceedings of the Third International Conference on Graphs and Optimization, GO-III (Leukerbad, 1998), Discrete Appl. Math. 94 (1999), pp. 161--169. MR 2000d:05066
H.M. Deng and Y.Q. Lin, A note on the path graph P_k(G) (Chinese), J. Xinjiang Univ. Natur. Sci. 16 (1999), no. 3, 16--20. MR 2000j:05048
R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51, (1950). 161--166. MR 11,309f
G. Ding, Recognizing the P₄-structure of a tree, Graphs Combin. 10 (1994), 323--328. MR 95k:05048
G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961) 71--76. MR 24 #A57
P. Duchet, Graphes noyau-parfaits, Combinatorics 79 (Proc. Colloq., Univ. Montréal, Montreal, Que., 1979), Part II, Ann. Discrete Math. 9 (1980), 93--101. MR 81k:05051
P. Duchet, Classical perfect graphs: an introduction with emphasis on triangulated and interval graphs, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 67--96. MR 86b:05029
P. Duchet, A sufficient condition for a digraph to be kernel-perfect, J. Graph Theory 11 (1987), 81--85. MR 88c:05059
P. Duchet, Parity graphs are kernel-M-solvable, J. Combin. Theory Ser. B 43 (1987), 121--126. MR 88j:05018
P. Duchet, On locally-perfect colorings.Graph colouring and variations, Discrete Math. 74 (1989), 29--32. MR 91d:05045
P. Duchet and H. Meyniel, A note on kernel-critical graphs, Discrete Math. 33 (1981), 103--105. MR 81k:05052
P. Duchet and H. Meyniel, Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientés, Discrete Math. 43 (1983), 21--27. MR 84g:05067
P. Duchet and S. Olariu, Graphes parfaitement ordonnables généralisés, Discrete Math. 90 (1991), 99--101. MR 92g:05135

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
H. Everett, C. M. H. de Figueiredo, C. Linhares-Sales, F. Maffray, O. Porto, and B. A. Reed, Path parity and perfection, Graphs and combinatorics (Marseille, 1995), Discrete Math. 165/166 (1997), 233--252. MR 98a:05069
H. Everett, C. M. H. de Figueiredo, C. Linhares Sales, F. Maffray, O. Porto, and B. A. Reed, Even pairs, in: Perfect Graphs (J.L. Ramírez-Alfonsín and B.A. Reed, eds.), Wiley, 2001, pp. 67--92. MR 1 861 358
H. Everett, S. Klein, and B. A. Reed, An algorithm for finding homogeneous pairs, Discrete Appl. Math. 72 (1997), no. 3, 209--218. MR 97k:05183

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
E. Fachini and J. Körner, Colour number, capacity, and perfectness of directed graphs, Graphs Combin. 16 (2000), 389--398. MR 2002g:05079
M. Farber, Characterizations of strongly chordal graphs, Discrete Math. 43 (1983), 173--189. MR 84c:05072
S. Felsner, R. Müller, and L. Wernisch, Lorenz, Trapezoid graphs and generalizations, geometry and algorithms, Algorithm theory---SWAT '94 (Aarhus, 1994), Lecture Notes in Comput. Sci. 824, Springer, Berlin, 1994, pp. 143--154. MR 95m:05223
C. M. H. de Figueiredo, Even pairs and bull-free perfect graphs, Graph theory, combinatorics, and algorithms, Vol. 1, 2 (Kalamazoo, MI, 1992), Wiley-Intersci. Publ., Wiley, New York, 1995, pp. 391--401. MR 97d:05100
C. M. H. de Figueiredo, S. Gravier, and C. Linhares Sales, On Tucker's proof of the strong perfect graph conjecture for $(K\sb 4-e)$-free graphs, Discrete Math 232 (2001), 105--108. MR 2002a:05119
C. M. H. de Figueiredo, S. Klein, Y. Kohayakawa, and B.A. Reed, Finding skew partitions efficiently, J. Algorithms 37 (2000), 505--521. MR 2001j:05114
C. M. H. de Figueiredo, F. Maffray, and O. Porto, On the structure of bull-free perfect graphs, Graphs Combin. 13 (1997), 31--55. MR 97m:05093
C. M. H. de Figueiredo, F. Maffray, and O. Porto, On the structure of bull-free perfect graphs. II. The weakly chordal case, Graphs Combin. 17 (2001), 435--456. MR 2002g:05093
C. M. H. de Figueiredo, J. Gimbel, C. Mello, and J. Szwarcfiter, Even and odd pairs in comparability and in P₄-comparability graphs, Discrete Appl. Math. 91 (1999), 293--297.
C. M. H. de Figueiredo, S. Klein, Y. Kohayakawa, and B. A. Reed, Finding skew partitions efficiently, Proceedings of LATIN 2000, Lecture Notes in Computer Science 1776 (2000), pp. 163--172.MR 2001j:05114
C. M. H. de Figueiredo and K. Vušković, A class of $\beta$-perfect graphs, Discrete Math. 216 (2000), 169--193. MR 2001b:05099
J. Fonlupt and A. Sebö, On the clique rank and the coloration of perfect graphs, Integer Programming and Combinatorial Optimization 1 (R. Kannan and W. R. Pulleyblank, eds.), University of Waterloo Press, 1990, pp. 201-229.
J. Fonlupt and J.-P. Uhry, Transformations which preserve perfectness and H-perfectness of graphs, Bonn Workshop on Combinatorial Optimization (Bonn, 1980), Ann. Discrete Math., 16, North-Holland, Amsterdam-New York, 1982, pp. 83--95. MR 84f:05076
J. Fonlupt and A. Zemirline, A characterization of perfect K₄-{e}-free graphs, Rev. Maghrébine Math. 1 (1992), 167--202. MR 97a:05181
J. Fonlupt and A. Zemirline, A polynomial recognition algorithm for perfect K₄-{e}-free graphs, Rev. Maghrébine Math. 2 (1993), 1--26. MR 96j:05100
J.-C. Fournier and M. Las Vergnas, Une classe d'hypergraphes bichromatiques, Discrete Math. 2 (1972), 407--410. MR 46 #5156
J.-C. Fournier and M. Las Vergnas, Une classe d'hypergraphes bichromatiques. II. Discrete Math. 7 (1974), 99--106. MR 49 #2446
J.-C. Fournier and M. Las Vergnas, A class of bichromatic hypergraphs, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 21--27. MR 86h:05080
J.-L. Fouquet, Perfect graphs with no 2K₂ and no K₆ (electronic), September 1999.
J.-L. Fouquet, On minimal imperfect NP₅ graphs (electronic), October 1999.
J.-L. Fouquet, V. Giakoumakis, F. Maire, and H. Thuillier, On graphs without P₅ and $\overline P₅$, Discrete Math. 146 (1995), 33--44. MR 96i:05142
J.-L. Fouquet, F. Maire, I. Rusu, and H. Thuillier, On transversals in minimal imperfect graphs, Graphs and combinatorics (Marseille, 1995), Discrete Math. 165/166 (1997), 301--312. MR 97m:05136
A. Frank, Some polynomial algorithms for certain graphs and hypergraphs, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), Congressus Numerantium, Utilitas Math., Winnipeg, Man., 1976, pp. 211--226. MR 52 #13500
D. R. Fulkerson, Note on Dilworth's decomposition theorem for partially ordered sets, Proc. Amer. Math. Soc. 7 (1956), 701--702. MR 17,1176g
D. R. Fulkerson, On perfect graph conjecture and pluperfect graph theorem , Proceedings of the Second Chapel Hill Conference on Combinatorial Mathematics and its Applications (Held at the University of North Carolina at Chapel Hill, May, 1970), Univ. North Carolina, Chapel Hill, N.C., 1970, pp. 171--175.
D. R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971), 168--194. MR 45 #3222
D. R. Fulkerson, Anti-blocking polyhedra, J. Combinatorial Theory Ser. B 12 (1972) 50--71. MR 44 #2629
D. R. Fulkerson, On the perfect graph theorem, Mathematical programming (Proc. Advanced Sem., Univ. Wisconsin, Madison, Wis., 1972), Math. Res. Center Publ., Academic Press, New York, 1973, pp. 69--76. MR 51 #10147
D. R. Fulkerson, A. J. Hoffman, and R. Oppenheim, On balanced matrices. Pivoting and extensions, Math. Programming Stud. (1974), 120--132. MR 56 #17042

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
H. Galeana-Sánchez, A counterexample to a conjecture of Meyniel on kernel-perfect graphs, Discrete Math. 41 (1982), 105--107. MR 85d:05124
H. Galeana-Sánchez, A counterexample to a conjecture of H. Meyniel on R-digraphs. (Spanish) Research program of the XVIIIth national congress of the Mexican Mathematical Society (Spanish) (Mérida, 1984), 220--227, Aportaciones Mat.: Comun., 1, Soc. Mat. Mexicana, Mexico City, 1986. MR 88f:05050
H. Galeana-Sánchez, A theorem about a conjecture of H. Meyniel on kernel-perfect graphs. Discrete Math. 59 (1986), 35--41. MR 87k:05085
H. Galeana-Sánchez, A new method to extend kernel-perfect graphs to kernel-perfect critical graphs, Discrete Math. 69 (1988), 207--209. MR 89d:05086
H. Galeana-Sánchez, Normal fraternally orientable graphs satisfy the strong perfect graph conjecture, Discrete Math. 122 (1993), 167--177. MR 94m:05079
H. Galeana-Sánchez, B₁- and B₂-orientable graphs in kernel theory, Discrete Math. 143 (1995), 269--274. MR 96c:05074
H. Galeana-Sánchez, On claw-free M-oriented critical kernel-imperfect digraphs, J. Graph Theory 21 (1996), 33--39. MR 96h:05089
H. Galeana-Sánchez, A characterization of normal fraternally orientable perfect graphs, Discrete Math. 169 (1997), 221--225. MR 98c:05060
H. Galeana-Sánchez and V. Neumann Lara, On kernels and semikernels of digraphs, Discrete Math. 48 (1984), 67--76. MR 85i:05115
H. Galeana-Sánchez and V. Neumann Lara, On kernel-perfect critical digraphs, Discrete Math. 59 (1986), 257--265. MR 88b:05069
H. Galeana-Sánchez and V. Neumann Lara, Extending kernel perfect digraphs to kernel perfect critical digraphs, Discrete Math. 94 (1991), 181--187. MR 92m:05089
H. Galeana-Sánchez and V. Neumann Lara, Orientations of graphs in kernel theory, Discrete Math. 87 (1991), 271--280. MR 92d:05134
H. Galeana-Sánchez and V. Neumann Lara, New extensions of kernel perfect digraphs to kernel imperfect critical digraphs, Graphs Combin. 10 (1994), 329--336. MR 95i:05064
H. Galeana-Sánchez and V. Neumann Lara , KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition, Discuss. Math. Graph Theory 16 (1996), 5--16. MR 97k:05098
H. Galeana-Sánchez and V. Neumann Lara, New classes of critical kernel-imperfect digraphs, Discuss. Math. Graph Theory 18 (1998), 85--89. MR 99g:05087
T. Gallai, Maximum-minimum Sätze über Graphen, Acta Math. Acad. Sci. Hungar. 9 (1958), 395--434. MR 23 #A1552b
T. Gallai, Über extreme Punkt- und Kantenmengen, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 2 (1959), 133--138. MR 24 #A1222
T. Gallai, Graphen mit triangulierbaren ungeraden Vielecken, Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 (1962) 3--36. MR 26 #3039
T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar 18 (1967) 25--66. MR 36 #5026
G. S. Gasparyan, Minimal imperfect graphs: a simple approach, Combinatorica 16 (1996), 209--212. MR 97c:05087
F. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Comput. 1 (1972), 180--187. MR 48 #5922
F. Gavril, An algorithm for testing chordality of graphs, Information Processing Lett. 3 (1974/75), 110--112. MR 52 #9671
F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combinatorial Theory Ser. B 16 (1974), 47--56. MR 48 #10868
F. Gavril, Algorithms on clique separable graphs, Discrete Math. 19 (1977), 159--165. MR 58 #10608
F. Gavril, V.Toledano Laredo, and D. de Werra, Chordless paths, odd holes, and kernels in graphs without m-obstructions, J. Algorithms 17 (1994), 207--221. MR 95h:05076
M. U. Gerber and A. Hertz, A transformation which preserves the clique number, J. Combin. Theory Ser. B 83 (2001), 320--330. MR 2002h:05127
S. Gerke and C. McDiarmid, Graph imperfection. I, II, J. Combin. Theory Ser. B 83 (2001), 58--78, 79--101. MR 1 855 796
D. Gernert, A survey of the strong perfect graph conjecture and some recent results, New York Graph Theory Day, 31 (1996), Graph Theory Notes N. Y. 31 (1996), 25--29. MR 99i:05080
D. Gernert, Properties of minimally imperfect graphs. Addendum to: "A survey of the strong perfect graph conjecture and some recent results", Graph Theory Notes N. Y. 32 (1997), 53. CMP 1 666 679
A. Ghouila-Houri, Caractérisation des graphes non orientés dont on peut orienter les arêtes de manière à obtenir le graphe d'une relation d'ordre. C. R. Acad. Sci. Paris 254 (1962) 1370--1371. MR 30 #2495
V. Giakoumakis, P₄-laden graphs: a new class of brittle graphs, Inform. Process. Lett. 60 (1996), 29--36. MR 97i:05108
V. Giakoumakis, On the closure of graphs under substitution, Discrete Math. 177 (1997), 83--97. MR 99g:05170
V. Giakoumakis and I. Rusu, Weighted parameters in (P₅, $\overline P₅$)-free graphs, Discrete Appl. Math. 80 (1997), 255--261. MR 98h:05167
R. Giles, L. E. Trotter, Jr., and A. Tucker, The strong perfect graph theorem for a class of partitionable graphs, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 161--167. MR 86j:05061
P. C. Gilmore and A. J. Hoffman, A characterization of comparability graphs and of interval graphs, Canad. J. Math. 16 (1964) 539--548. MR 31 #87
M. C. Golumbic, Comparability graphs and a new matroid, J. Combinatorial Theory Ser. B 22 (1977), 68--90. MR 55 #12575
M. C. Golumbic, Algorithmic graph theory and perfect graphs. With a foreword by Claude Berge. Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London-Toronto, Ont., 1980. xx+284 pp. ISBN: 0-12-289260-7 MR 81e:68081
M. C. Golumbic, Algorithmic aspects of perfect graphs, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 301--323. MR 86g:05072
M. C. Golumbic, C.L. Monma, and W. T. Trotter, Jr., Tolerance graphs, Discrete Appl. Math. 9 (1984), 157--170. MR 86b:05063
C. Greene, Some partitions associated with a partially ordered set, J. Combinatorial Theory Ser. A 20 (1976), 69--79. MR 53 #2763
C. Greene and D. J. Kleitman, The structure of Sperner k-families, J. Combinatorial Theory Ser. A 20 (1976), 41--68. MR 53 #2695
C. M. Grinstead, The strong perfect graph conjecture for toroidal graphs, J. Combin. Theory Ser. B 30 (1981), 70--74. MR 82d:05087
C. M. Grinstead, The perfect graph conjecture for toroidal graphs, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 97--101. MR 86e:05080
C. M. Grinstead, On circular critical graphs, Discrete Math. 51 (1984), 11--24. MR 86g:05080
M. Grötschel, Characterizations of perfect graphs, Optima 62 (June 1999), 2--5.
M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (1981), 169--197. MR 84a:90044 (Corrigendum in Combinatorica 4 (1984), 291--295. MR 86c:90077)
M. Grötschel, L. Lovász, and A. Schrijver, Geometric methods in combinatorial optimization, Progress in combinatorial optimization (Waterloo, Ont., 1982), Academic Press, Toronto, Ont., 1984, pp. 167--183. MR 86d:90127
M. Grötschel, L. Lovász, and A. Schrijver, Polynomial algorithms for perfect graphs, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 325--356. MR 86g:05073
M. Grötschel, L. Lovász, and A. Schrijver, Relaxations of vertex packing, J. Combin. Theory Ser. B 40 (1986), 330--343. MR 87h:05087
M. Grötschel, L. Lovász, and A. Schrijver, Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics: Study and Research Texts, 2, Springer-Verlag, Berlin-New York, 1988. xii+362 pp. ISBN: 3-540-13624-X MR 89m:90135 (Second edition 1993, ISBN: 3-540-56740-2 MR 95e:90001)
V. A. Gurvich, Bilinear forms of enumerated graphs.(Russian) Dokl. Akad. Nauk 325 (1992), 221--226; translation in Russian Acad. Sci. Dokl. Math. 46 (1993), 36--42 MR 94d:05115
V. A. Gurvich, Renumbered graphs and their bilinear forms.(Russian) Uspekhi Mat. Nauk 47 (1992), 189--190; translation in Russian Math. Surveys 47 (1992), 206--207 MR 94d:05116
V. A. Gurvich, Biseparated graphs are perfect.(Russian) Dokl. Akad. Nauk 331 (1993), 541--545. MR 94k:05159
V. A. Gurvich, Completely separated and biseparated graphs.(Russian) Dokl. Akad. Nauk 328 (1993), 427--430. MR 94d:05055
V. A. Gurvich, Cyclic bilinear forms of enumerated graphs.(Russian) Dokl. Akad. Nauk 331 (1993), 11--13. MR 94f:05145
V. A. Gurvich, The generalized Lovász inequality for perfect graphs.(Russian) Uspekhi Mat. Nauk 48 (1993), 175--176. MR 94f:05053
V. A. Gurvich and M. A. Temkin, Cellular perfect graphs.(Russian) Dokl. Akad. Nauk 326 (1992), 227--232. MR 93m:05069
V. A. Gurvich and M. A. Temkin, Berge's conjecture holds for rotational graphs.(Russian) Dokl. Akad. Nauk 332 (1993), 144--148. MR 94m:05156
V. A. Gurvich, M. A. Temkin, V. M. Udalov, and A. V. Shapovalov, Rotational graphs without odd holes and antiholes.(Russian) Dokl. Akad. Nauk 329 (1993), 411--415; translation in Russian Acad. Sci. Dokl. Math. 47 (1993), 278--284 MR 94j:05103
D. Gusfield, Partition-distance: a problem and class of perfect graphs arising in clustering, Inform. Process. Lett. 82 (2002), 159--164. MR 1 893 065
A. Gyárfás, Problems from the world surrounding perfect graphs, Tanulmányok---MTA Számitástech. Automat. Kutató Int. Budapest (1985), 53 pp. MR 88a:05066
A. Gyárfás, Problems from the world surrounding perfect graphs, Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), Zastos. Mat. 19 (1987), 413--441 (1988). MR 89e:05089
A. Gyárfás, D. Kratsch, J. Lehel, and F. Maffray, Minimal non-neighborhood-perfect graphs, J. Graph Theory 21 (1996), 55--66. MR 96m:05081

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
W. Haemers, On some problems of Lovász concerning the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), 231--232. MR 80g:94040
A. Hajnal and J. Surányi, Über die Auflösung von Graphen in vollständige Teilgraphen. Ann. Univ. Sci. Budapest. Eötvös. Sect. Math. 1 (1958) 113--121. MR 21 #1944
P. L. Hammer and N. V. R. Mahadev, Bithreshold graphs, SIAM J. Algebraic Discrete Methods 6 (1985), 497--506. MR 86h:05093
P. L. Hammer and F. Maffray, Preperfect graphs, Combinatorica 13 (1993), 199--208. MR 94e:05107
F. Harary and C. Holzmann, Line graphs of bipartite graphs, Rev. Soc. Mat. Chile 1 (1974), 19--22.
R. B. Hayward, Weakly triangulated graphs, J. Combin. Theory Ser. B 39 (1985), 200--208. MR 87h:05171
R. B. Hayward, Murky graphs, J. Combin. Theory Ser. B 49 (1990), 200--235. MR 91f:05053
R. B. Hayward, Discs in unbreakable graphs, Graphs Combin. 11 (1995), 249--254. MR 96m:05123
R. B. Hayward, Generating weakly triangulated graphs, J. Graph Theory 21 (1996), 67--69. MR 96g:05049
R. B. Hayward, Recognizing P₃-structure: a switching approach, J. Combin. Theory Ser. B 66 (1996), 247--262. MR 96m:05168
R. B. Hayward, Meyniel weakly triangulated graphs. I. Co-perfect orderability, Discrete Appl. Math. 73 (1997), 199--210. MR 98e:05039
R. B. Hayward, Meyniel weakly triangulated graphs. II. A theorem of Dirac, Discrete Appl. Math. 78 (1997), 283--289. MR 99b:05037
R. B. Hayward, Bull-free Weakly Triangulated Perfectly Orderable Graphs (electronic).
R. B. Hayward, C. T. Hoàng, and F. Maffray, Optimizing weakly triangulated graphs, Graphs Combin. 5 (1989), 339--349. MR 91c:68051a. Erratum in Graphs Combin. 6 (1990), 33--35. MR 91c:68051b
R. B. Hayward and W. J. Lenhart, On the P₄-structure of perfect graphs. IV. Partner graphs, J. Combin. Theory Ser. B 48 (1990), 135--139. MR 91i:05056
R. Hayward and B. A. Reed, Forbidding holes and antiholes, in: Perfect Graphs (J.L. Ramírez-Alfonsín and B.A. Reed, eds.), Wiley, 2001, pp. 113--137. MR 1 861 360
R. B. Hayward, J. Spinrad, and R. Sritharan, Weakly chordal graph algorithms via handles, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), ACM, New York, 2000, pp. 42--49. CMP 1 754 839
S. T. Hedetniemi, Graphs of (0,1)-matrices, Recent Trends in Graph Theory (Proc. Conf., New York, 1970), Lecture Notes in Mathematics, Vol. 186. Springer, Berlin, 1971, pp. 157--171. MR 43 #6120
A. Hertz, Bipartable graphs, J. Combin. Theory Ser. B 45 (1988), 1--12. MR 89i:05116
A. Hertz, Skeletal graphs---a new class of perfect graphs, Discrete Math. 78 (1989), 291--296. MR 90i:05079
A. Hertz, Slender graphs, J. Combin. Theory Ser. B 47 (1989), 231--236. MR 91a:05078
A. Hertz, Slim graphs, Graphs Combin. 5 (1989), 149--157. MR 90f:05060
A. Hertz, A fast algorithm for coloring Meyniel graphs, J. Combin. Theory Ser. B 50 (1990), 231--240. MR 91i:05111
A. Hertz, Bipolarizable graphs, Discrete Math. 81 (1990), 25--32. MR 91b:05154
A. Hertz, On perfect switching classes, Discrete Appl. Math. 89 (1998), 263--267. MR 99g:05077
A. Hertz, On perfect switching classes, Proceedings of the Third International Conference on Graphs and Optimization, GO-III (Leukerbad, 1998), Discrete Appl. Math. 94 (1999), 3--7. MR 2000d:05050
A. Hertz and D. de Werra, Perfectly orderable graphs are quasiparity graphs: a short proof, Discrete Math. 68 (1988), 111--113. MR 88m:05067
Y. Hiraishi and T. Sakuma, On the flip operations of clique-acyclic orientations of graphs, Proceedings of the 10th Workshop on Topological Graph Theory (Yokohama, 1998), Yokohama Math. J. 47 (1999), Special Issue, 143--163. MR 2001j:05060
C. T. Hoàng, On the P₄-structure of perfect graphs. II. Odd decompositions, J. Combin. Theory Ser. B 39 (1985), 220--232. MR 87c:05056b
C. T. Hoàng, Alternating orientation and alternating colouration of perfect graphs, J. Combin. Theory Ser. B 42 (1987), 264--273. MR 88i:05082
C. T. Hoàng, On a conjecture of Meyniel, J. Combin. Theory Ser. B 42 (1987), 302--312. MR 88e:05040
C. T. Hoàng, On the sibling-structure of perfect graphs, J. Combin. Theory Ser. B 49 (1990), 282--286. MR 91h:05054
C. T. Hoàng, Efficient algorithms for minimum weighted colouring of some classes of perfect graphs, Discrete Appl. Math. 55 (1994), 133--143. MR 95k:68175
C. T. Hoàng, On the two-edge-colorings of perfect graphs, J. Graph Theory 19 (1995), 271--279. MR 96e:05054
C. T. Hoàng, A note on perfectly orderable graphs, First International Colloquium on Graphs and Optimization (GOI), 1992 (Grimentz), Discrete Appl. Math. 65 (1996), 379--386. MR 97a:05184
C. T. Hoàng, On the complexity of recognizing a class of perfectly orderable graphs, Discrete Appl. Math. 66 (1996), 219--226. MR 97a:68080
C. T. Hoàng, Some properties of minimal imperfect graphs, Discrete Math. 160 (1996), 165--175. MR 97h:05067
C. T. Hoàng, On the disc-structure of perfect graphs. I. The co-paw-structure, Proceedings of the Third International Conference on Graphs and Optimization, GO-III (Leukerbad, 1998), Discrete Appl. Math. 94 (1999), 247--262. MR 2001a:05065
C. T. Hoàng, S. Hougardy, and F. Maffray, On the P₄-structure of perfect graphs. V. Overlap graphs, J. Combin. Theory Ser. B 67 (1996), 212--237. MR 97f:05068
C. T. Hoàng, Perfectly orderable graphs: a survey, in: Perfect Graphs (J.L. Ramírez-Alfonsín and B.A. Reed, eds.), Wiley, 2001, pp. 139--166. MR 1 861 361
C. T. Hoàng and N. Khouzam, On brittle graphs, J. Graph Theory 12 (1988), 391--404. MR 90b:05110
C. T. Hoàng and V. B. Lê, On P₄-transversals of perfect graphs, Discrete Math. 216 (2000), 195--210. MR 2000m:05103
C. T. Hoàng and V. B. Lê, Recognizing perfect 2-split graphs, SIAM J. Discrete Math. 13 (2000), 48--55 (electronic). MR 2000k:05122
C. T. Hoàng and V. B. Lê, P₄-free colorings and P₄-bipartite graphs, Discrete Math. Theor. Comput. Sci. 4 (2001), 109--122 (electronic). MR 1 835 588
C. Hoàng and C. McDiarmid, On the divisibility of graphs, Discrete Math. 242 (2002), 145--156. MR1874761 (2002j:05110)
C. T. Hoàng and F. Maffray, Opposition graphs are strict quasi-parity graphs, Graphs Combin. 5 (1989), 83--85. MR 89m:05097
C. T. Hoàng and F. Maffray, On slim graphs, even pairs, and star-cutsets, Discrete Math. 105 (1992), 93--102. MR 93h:05132
C. T. Hoàng, F. Maffray, and M. Noy, A characterization of P₄-indifference graphs, J. Graph Theory 31 (1999), 155--162. MR 2000c:05121
C. T. Hoàng, F. Maffray, S. Olariu, and M. Preissmann, A charming class of perfectly orderable graphs, Discrete Math. 102 (1992), 67--74. MR 93b:05140
C. T. Hoàng, F. Maffray, and M. Preissmann, New properties of perfectly orderable graphs and strongly perfect graphs, Discrete Math. 98 (1991), 161--174. MR 92m:05082
C. T. Hoàng and N. V. R. Mahadev, A note on perfect orders. Graph colouring and variations, Discrete Math. 74 (1989), 77--84. MR 90d:05098
C. T. Hoàng and B. A. Reed, Some classes of perfectly orderable graphs, J. Graph Theory 13 (1989), 445--463. MR 90f:05117
C. T. Hoàng and B. A. Reed, P₄-comparability graphs. Graph colouring and variations, Discrete Math. 74 (1989), 173--200. MR 89m:05098
A. J. Hoffman, A. W. J. Kolen, and M. Sakarovitch, Totally-balanced and greedy matrices, SIAM J. Algebraic Discrete Methods 6 (1985), 721--730. MR 86j:90089
S. Hougardy, Counterexamples to three conjectures concerning perfect graphs, Discrete Math. 117 (1993), 245--251. MR 94b:05080
S. Hougardy, Even and odd pairs in linegraphs of bipartite graphs, European J. Combin. 16 (1995), 17--21. MR 95m:05195
S. Hougardy, Even pairs and the strong perfect graph conjecture, Discrete Math. 154 (1996), 277--278. MR 97a:05086
S. Hougardy, On the P₄-Structure of Perfect Graphs (electronic introduction), Dissertation, Shaker Verlag, Aachen, 1996, ISBN 3-8265-1140-9
S. Hougardy, Gasparian's Proof of the Perfect Graph Theorem (electronic), Humboldt-Universität zu Berlin, January 1997.
S. Hougardy, Perfect graphs with unique P₄-structure, Graphs and combinatorics (Marseille, 1995), Discrete Math. 165/166 (1997), 421--430. MR 97m:05098
S. Hougardy, Inclusions between classes of perfect graphs, (electronic), Manuscript, Humboldt-Universität zu Berlin, May 1998.
S. Hougardy, On wing-perfect graphs, J. Graph Theory 31 (1999), 51--66. MR 2000e:05075
S. Hougardy, On a conjecture of Hoàng and Tu concerning perfectly orderable graphs (electronic), Humboldt-Universität zu Berlin, October 1999
S. Hougardy, V. B. Lê, and A. Wagler, Wing-triangulated graphs are perfect, J. Graph Theory 24 (1997), 25--31. MR 97j:05025
S. Hougardy, The P₄-structure of perfect graphs, in: Perfect Graphs (J.L. Ramírez-Alfonsín and B.A. Reed, eds.), Wiley, 2001, pp. 93--112.MR 2002h:05075
W.-L. Hsu, How to color claw-free perfect graphs, Studies on graphs and discrete programming (Brussels, 1979), Ann. Discrete Math., 11, North-Holland, Amsterdam-New York, 1981, pp. 189--197. MR 83h:05037
W.-L. Hsu, The perfect graph conjecture on special graphs---a survey, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 103--113. MR 86m:05043
W.-L. Hsu, Coloring planar perfect graphs by decomposition, Combinatorica 6 (1986), 381--385. MR 88b:05055
W.-L. Hsu, The coloring and maximum independent set problems on planar perfect graphs, J. Assoc. Comput. Mach. 35 (1988), 535--563. MR 89m:68049
W.-L. Hsu, Recognizing planar perfect graphs, J. Assoc. Comput. Mach. 34 (1987), 255--288. MR 88j:68145
W.-L. Hsu, The coloring and maximum independent set problems on planar perfect graphs, J. Assoc. Comput. Mach. 35 (1988), 535--563. MR 89m:68049
W.-L. Hsu and G. L. Nemhauser, Algorithms for minimum covering by cliques and maximum clique in claw-free perfect graphs, Discrete Math. 37 (1981), 181--191. MR 84i:05066
W.-L. Hsu and G. L. Nemhauser, A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs, Discrete Math. 38 (1982), 65--71. MR 84g:68051
W.-L. Hsu and G. L. Nemhauser, Algorithms for maximum weight cliques, minimum weighted clique covers and minimum colorings of claw-free perfect graphs, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 357--369. MR 87f:05091
S. M. Huang, Cartan matrices and strong perfect graph conjecture, Graph theory, combinatorics, and applications. Vol. 2 (Kalamazoo, MI, 1988), Wiley-Intersci. Publ., Wiley, New York, 1991, pp. 681--686. CMP 1 170 816
Y. Huang and X. Guo, On a class of kernel-perfect and kernel-perfect-critical graphs, J. Xinjiang Univ. Natur. Sci. 16 (1999), 1--9. MR 2000m:05106
M. Hujter, Combinatorial ranks of matrices, Publ. Univ. Miskolc Ser. D Nat. Sci. Math. 40 (1999), 35--46.MR 2001a:05066

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
H. Jacob and H. Meyniel, Extension of Turán's and Brooks' theorems and new notions of stability and coloring in digraphs, Combinatorial mathematics (Marseille-Luminy, 1981), North-Holland Math. Stud., 75, North-Holland, Amsterdam-New York, 1983, pp. 365--370. MR 87h:05089
B. Jamison and S. Olariu, On a class of P₅-free graphs, Stud. Appl. Math. 81 (1989), 33--39. MR 90g:05082
B. Jamison and S. Olariu, p-components and the homogeneous decomposition of graphs, SIAM J. Discrete Math. 8 (1995), 448--463. MR 96i:05105
K. Jansen, A new characterization for parity graphs and a coloring problem with costs, LATIN'98: theoretical informatics (Campinas, 1998), Lecture Notes in Comput. Sci., 1380, Springer, Berlin, 1998, pp. 249--260. MR 99e:05051
T. R. Jensen and B. Toft, Graph coloring problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1995. xxii+295 pp. ISBN: 0-471-02865-7 MR 95h:05067
E. L. Johnson and M. W. Padberg, Degree-two inequalities, clique facets, and biperfect graphs, Bonn Workshop on Combinatorial Optimization (Bonn, 1980), Ann. Discrete Math., 16, North-Holland, Amsterdam-New York, 1982, pp. 169--187. MR 84j:05085

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
J. Kahn, A family of perfect graphs associated with directed graphs, J. Combin. Theory Ser. B 37 (1984), 279--282. MR 86a:05053
I. A. Karapetyan, Critical and essential edges in perfect graphs.(Russian) Akad. Nauk Armjan. SSR Dokl. 63 (1976), 65--70. MR 58 #21757
A. K. Kelmans, 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.
A. K. Kelmans, The strong perfect graph conjecture for a certain class of graphs, XXVII. Internationales Wissenschaftliches Kolloquium Technische Hochschule Ilmenau -- 1982.
T. King and G. L. Nemhauser, Some inequalities on the chromatic number of a graph, Discrete Math. 10 (1974), 117--121. MR 50 #1953
D.E. Knuth, The sandwich theorem, Electron. J. Combin. 1 (1994), Article 1, approx. 48 pp. (electronic). MR 95g:05048a
J. Körner, An extension of the class of perfect graphs, Studia Sci. Math. Hungar. 8 (1973), 405--409. MR 58 #5402
J. Körner, G. Simonyi, and Zs. Tuza, Perfect couples of graphs, Combinatorica 12 (1992), 179--192. MR 93i:05107
M. J. Król, The chromatic number of some 2-connected graphs, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), Academia, Prague, 1975, pp. 335--340. MR 53 #5354
L. G. Kroon, A. Sen, H. Deng, and A. Roy, The optimal cost chromatic partition problem for trees and interval graphs, Graph-theoretic concepts in computer science (Cadenabbia, 1996), Lecture Notes in Comput. Sci. 1197, Springer, Berlin, 1997, pp. 279--292. MR 98f:05062
M. Kwasnik and A. Szelecka, Strong perfectness of the generalized Cartesian product of graphs, The Second Krakow Conference on Graph Theory (Zgorzelisko, 1994), Discrete Math. 164 (1997), 213--220. MR 97h:05068

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
C. W. H. Lam, S. Swiercz, L. Thiel, E. Regener, A computer search for $(\alpha ,\omega )$-graphs, Proceedings of the Ninth Manitoba Conference on Numerical Mathematics and Computing (Univ. Manitoba, Winnipeg, Man., 1979), Congress. Numer., XXVII, Utilitas Math., Winnipeg, Man., 1980, pp. 285--289. MR 82b:05002
M. Las Vergnas, Sur les hypergraphes bichromatiques, Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross), Lecture Notes in Math., Vol. 411, Springer, Berlin, 1974, pp. 102--110. MR 51 #10150
V. B. Lê, Mortality of iterated Gallai graphs, Period. Math. Hungar. 27 (1993), 105--124. MR 95g:05087
V. B. Lê, Perfect k-line graphs and k-total graphs, J. Graph Theory 17 (1993), 65--73. MR 94b:05083
V. B. Lê, Cycle-perfect graphs are perfect, J. Graph Theory 23 (1996), 351--353. MR 97j:05027
V. B. Lê, Gallai graphs and anti-Gallai graphs, Discrete Math. 159 (1996), 179--189. MR 98b:05043
V. B. Lê, Some Conjectures on Perfect Graphs, Discuss. Math. Graph Theory 20 (2000), 155--159. CMP 1 781 505
J. Lehel, A characterization of totally balanced hypergraphs, Discrete Math. 57 (1985), 59--65. MR 87f:05123
J. Lehel and Zs. Tuza, Neighborhood perfect graphs, Discrete Math. 61 (1986), 93--101. MR 87j:05128
J. Lehel, Peripheral graphs, Eighteenth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Fla., 1987), Congr. Numer. 59 (1987), 179--184. MR 89e:05171
J. Lehel, Neighbourhood-perfect line graphs, Graphs Combin. 10 (1994), 353--361. MR 95j:05150
Y.Q. Lin, Perfect path graphs P₃(G) (Chinese), J. Math. Study 30 (1997), 317--318. CMP 1 606 284
Y.Q. Lin, A note on the perfect 3-total graphs (Chinese), J. Guangxi Univ. Nat. Sci. Ed. 23 (1998), 242--245. CMP 1 716 457
C. Linhares-Sales, F. Maffray, and B. A. Reed, On planar perfectly contractile graphs, Graphs Combin. 13 (1997), 167--187. MR 98e:05093
C. Linhares-Sales and F. Maffray, Even pairs in claw-free perfect graphs, J. Combin. Theory Ser. B 74 (1998), 169--191. MR 2000b:05061
Z. Lonc and L. S. Zaremba, SPGC is true if it holds for all doubly short chord graphs, Ulam Quart. 3 (1995), 1 ff., approx. 7 pp. (electronic). MR 96m:05087
L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972), 253--267. MR 46 #1624
L. Lovász, A characterization of perfect graphs, J. Combinatorial Theory Ser. B 13 (1972), 95--98. MR 46 #8885
L. Lovász, Minimax theorems for hypergraphs, Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross), Lecture Notes in Math., Vol. 411, Springer, Berlin, 1974, pp. 111--126. MR 53 #10648
L. Lovász, On two minimax theorems in graph, J. Combinatorial Theory Ser. B 21 (1976), 96--103. MR 55 #174
L. Lovász, On minimax theorems of combinatorics.(Hungarian) Mat. Lapok 26 (1975), 209--264 (1978). MR 80a:05157
L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), 1--7. MR 81g:05095
L. Lovász, Perfect graphs, Selected topics in graph theory (L. M. Beineke and R. L. Wilson, eds.), 2, Academic Press, London-New York, 1983, pp. 55--87. MR 86h:05053
L. Lovász, Normal hypergraphs and the weak perfect graph conjecture, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 29--42. MR 86g:05068
L. Lovász, An algorithmic theory of numbers, graphs and convexity. CBMS-NSF Regional Conference Series in Applied Mathematics, 50, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1986. iv+91 pp. ISBN: 0-89871-203-3 MR 87m:68066
L. Lovász, Stable sets and polynomials. Graphs and combinatorics (Qawra, 1990), Discrete Math. 124 (1994), 137--153. MR 95a:05052
L. Lovász and A. Schrijver, Matrix cones, projection representations, and stable set polyhedra, Polyhedral combinatorics (Morristown, NJ, 1989), 1--17, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 1, Amer. Math. Soc., Providence, RI, 1990. MR 92c:52016
L. Lovász and A. Schrijver, Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim. 1 (1991), 166--190. MR 92b:05072
A. Lubiw, Doubly lexical orderings of matrices, SIAM J. Comput. 16 (1987), 854--879. MR 88m:68051
A. Lubiw, Short-chorded and perfect graphs, J. Combin. Theory Ser. B 51 (1991), 24--33. MR 92a:05095
A. Lubiw, A note on odd/even cycles, Discrete Appl. Math. 22 (1988/89), 87--92. MR 90a:05118

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
C. McDiarmid, Graph imperfection and channel assignment, in: Perfect Graphs (J.L. Ramírez-Alfonsín and B.A. Reed, eds.), Wiley, 2001, pp. 215--231.MR 2002h:05076
F. R. McMorris, C. Wang, P. Zhang, On probe interval graphs, Discrete Appl. Math. 88 (1998), 315--324. MR 99k:92020
F. Maffray, On kernels in i-triangulated graphs, Discrete Math. 61 (1986), 247--251. MR 87i:05098
F. Maffray, Kernels in perfect line-graphs, J. Combin. Theory Ser. B 55 (1992), 1--8. MR 93i:05061
F. Maffray, Antitwins in partitionable graphs, Discrete Math. 112 (1993), 275--278. MR 94e:05112
F. Maffray, O. Porto, and M. Preissmann, A generalization of simplicial elimination orderings, J. Graph Theory 23 (1996), 203--208. MR 98e:05044
F. Maffray and M. Preissmann, Perfect graphs with no P₅ and no K₅, Graphs Combin. 10 (1994), 179--184. MR 95g:05074
F. Maffray and M. Preissmann, Split-neighbourhood graphs and the strong perfect graph conjecture, J. Combin. Theory Ser. B 63 (1995), 294--309. MR 96d:05083
F. Maffray and M. Preissmann, Sequential colorings and perfect graphs, Proceedings of the Third International Conference on Graphs and Optimization, GO-III (Leukerbad, 1998), Discrete Appl. Math. 94 (1999), 287--296. MR 2001a:05062
F. Maffray and B. A. Reed, A description of claw-free perfect graphs, J. Combin. Theory Ser. B 75 (1999), 134--156. MR 2000b:05062
F. Maffray and N. Trotignon, A class of perfectly contractile graphs, Les cahiers du laboratoire Leibniz 67 (December 2002)
F. Maire, Slightly triangulated graphs are perfect, Graphs Combin. 10 (1994), 263--268. MR 96b:05063
F. Maire, Polyominos and perfect graphs, Inform. Process. Lett. 50 (1994), 57--61. MR 95h:05045
F. Maire, Optimizing slightly triangulated graphs, Australas. J. Combin. 14 (1996), 5--13. MR 97g:05142
E. Mândrescu, Strongly perfect products of graphs, Czechoslovak Math. J. 41(116) (1991), 368--372. MR 92d:05111
S. E. Markosyan, Perfect and critical graphs. (Russian) Akad. Nauk Armjan. SSR Dokl. 60 (1975), 218--223. MR 53 #10659
S. E. Markosyan, Berge's conjecture. (Russian) Applied mathematics, 41--46, 91--92, Erevan. Univ., Erevan, 1981. MR 87k:05082
A. S. Markosyan, Nonperfect critical graphs containing an incomplete critical component. (Russian) Erevan. Gos. Univ. Uchen. Zap. Estestv. Nauki 1985, 33--37.
S. E. Markosyan, Essentially perfect and essentially diperfect graphs.(Russian) Izv. Nats. Akad. Nauk Armenii Mat. 31 (1996), 34--43 (1999); translation in J. Contemp. Math. Anal. 31 (1996), 28--36 (1997) MR 2000d:05051
S. E. Markosyan, Critical subgraphs and critical sets of graphs.(Russian) Dokl. Akad. Nauk Armen. 97 (1997), 7--11. MR 99k:05094
S. E. Markosyan and G. S. Gasparyan, On the Berge conjecture.(Russian) Akad. Nauk Armyan. SSR Dokl. 85 (1987), 56--59. MR 89b:05142
S. E. Markosyan, G. S. Gasparyan, I. A. Karapetyan, and A. S. Markosyan, On essential components and critical sets of a graph, Discrete Math. 178 (1998), 137--153. MR 98m:05167
S. E. Markosyan, G. S. Gasparyan, and A. S. Markosyan, On a conjecture of Berge, J. Combin. Theory Ser. B 56 (1992), 97--107. MR 93h:05078
S. E. Markosyan and I. A. Karapetyan, Perfect graphs.(in Russian with an Armenian summary), Akad. Nauk Armjan. SSR Dokl. 63 (1976), 292--296. MR 56 #8427
S. E. Markosyan and I. A. Karapetyan, Critically imperfect graphs. (Russian) Applied mathematics, 131--138, 164, Erevan. Univ., Erevan, 1984. MR 86k:05098
H. Meyniel, On the perfect graph conjecture, Discrete Math. 16 (1976), 339--342. MR 55 #12568
H. Meyniel, The graphs whose odd cycles have at least two chords, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 115--119. MR 87d:05080
H. Meyniel, A new property of critical imperfect graphs and some consequences, European J. Combin. 8 (1987), 313--316. MR 88k:05082
H. Meyniel and S. Olariu, A new conjecture about minimal imperfect graphs, J. Combin. Theory Ser. B 47 (1989), 244--247. MR 91b:05118
M. Middendorf and F. Pfeiffer, On the complexity of recognizing perfectly orderable graphs, Discrete Math. 80 (1990), 327--333. MR 91b:68038
R. H. Möhring, Algorithmic aspects of comparability graphs and interval graphs, Graphs and order (Banff, Alta., 1984), NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., 147, Reidel, Dordrecht-Boston, Mass., 1985, pp. 41--101. MR 87d:05142
R. H. Möhring, Algorithmic aspects of the substitution decomposition in optimization over relations, sets systems and Boolean functions, Ann. Oper. Res. 4 (1985), 195--225. MR 89b:90175
C. L. Monma and L. E. Trotter, Jr., On perfect graphs and polyhedra with (0,1)-valued extreme points, Math. Programming 17 (1979), 239--242. MR 80i:90070
H. Müller, On edge perfectness and classes of bipartite graphs, Discrete Math. 149 (1996), 159--187. MR 97f:05069
J. H. Muller and J. Spinrad, Incremental modular decomposition, J. Assoc. Comput. Mach. 36 (1989), 1--19. MR 91i:68119

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
G. L. Nemhauser and L. E. Trotter, Jr., Properties of vertex packing and independence system polyhedra, Math. Programming 6 (1974), 48--61. MR 52 #200
G. L. Nemhauser and L. E. Trotter, Jr., Vertex packings: structural properties and algorithms, Math. Programming 8 (1975), 232--248. MR 51 #2985

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
S. Olariu, All variations on perfectly orderable graphs, J. Combin. Theory Ser. B 45 (1988), 150--159. MR 89i:05120
S. Olariu, Coercion classes in unbreakable graphs, Eleventh British Combinatorial Conference (London, 1987), Ars Combin. 25 (1988), B, 153--180. MR 89d:05152
S. Olariu, No antitwins in minimal imperfect graphs, J. Combin. Theory Ser. B 45 (1988), 255--257. MR 89g:05050
S. Olariu, On the strong perfect graph conjecture, J. Graph Theory 12 (1988), 169--176. MR 89b:05088
S. Olariu, Paw-free graphs, Inform. Process. Lett. 28 (1988), 53--54. MR 89h:05033
S. Olariu, A decomposition for strongly perfect graphs, J. Graph Theory 13 (1989), 301--311. MR 90d:05101
S. Olariu, The strong perfect graph conjecture for pan-free graphs, J. Combin. Theory Ser. B 47 (1989), 187--191. MR 91b:05080
S. Olariu, A generalization of Chvátal's star-cutset lemma, Inform. Process. Lett. 33 (1990), 301--303. MR 91a:05082
S. Olariu, Wings and perfect graphs, Discrete Math. 80 (1990), 281--296. MR 91e:05032
S. Olariu, On the structure of unbreakable graphs, J. Graph Theory 15 (1991), 349--373. MR 92i:05097
S. Olariu, Quasi-brittle graphs, a new class of perfectly orderable graphs, Discrete Math. 113 (1993), 143--153. MR 94b:05087
S. Olariu and I. A. Stewart, A new characterization of unbreakable graphs, Internat. J. Found. Comput. Sci. 4 (1993), 193--196. MR 94j:05092
E. Olaru, Über die Überdeckung von Graphen mit Cliquen, Wiss. Z. Techn. Hochsch. Ilmenau 15 (1969) Heft 4/5, 115--121. MR 43 #3162
E. Olaru, Eine Anwendung der $\alpha $-zerlegbaren Graphen in der Informationstheorie. An. \c Sti. Univ. "Al. I. Cuza" Ia\c si Sec\c t. I a Mat. (N.S.) 17 (1971), 275--285. MR 56 #5366
E. Olaru, Beiträge zur Theorie der perfekten Graphen. (English and Russian summaries) Elektron. Informationsverarbeit. Kybernetik 8 (1972), 147--172. MR 47 #8338
E. Olaru, Über kritisch imperfekte Graphen und die starke Vermutung der perfekten Graphen, Theorie der Graphen und Netzwerke XVIII, Int. Wiss. Koll. TH Ilmenau 1973, 19-22.
E. Olaru, Über perfekte und kritisch imperfekte Graphen. (Romanian summary) An. \c Sti. Univ. "Al. I. Cuza" Ia\c si Sec\c t. I a Mat. (N.S.) 19 (1973), 477--486. MR 54 #5053
E. Olaru, Zur Charakterisierung perfekter Graphen. (English and Russian summaries) Elektron. Informationsverarbeit. Kybernetik 9 (1973), 543--548. MR 51 #10167
E. Olaru, Zur Theorie der perfekten Graphen, J. Combinatorial Theory Ser. B 23 (1977), 94--105. MR 58 #5411
E. Olaru, $\alpha $-zerlegbare Graphen, Bul. Univ. Gala\cedla ti Fasc. II Mat. Fiz. Mec. Teoret. 3 (1980), 39--45. MR 83i:05048
E. Olaru, On the strongly perfect and the minimal strongly imperfect graphs, An. Univ. Gala\c ti Metal. 5(10) (1987), 5--9. MR 89i:05121
E. Olaru, On strongly perfect graphs and the structure of critically-imperfect graphs, An. \c Stiin\c t. Univ. Al. I. Cuza Ia\c si Inform. (N.S.) 2 (1993), 45--59. MR 96c:05150
E. Olaru, The structure of imperfect critically strongly-imperfect graphs, Discrete Math. 156 (1996), 299--302. MR 97c:05065
E. Olaru, On strongly stable graphs and some consequences for partitionable graphs, An. \c Stiin\c t. Univ. Al. I. Cuza Ia\c si Inform. (N.S.) 7 (1998), 33--41 (1999). MR 2000a:05172
E. Olaru, On strongly stable graphs and some consequences for partitionable graphs, ROSYCS'98 (Ia\c si), An. \c Stiin\c t. Univ. Al. I. Cuza Ia\c si Inform. (N.S.) 8 (1999), 121--128 (2000).
E. Olaru, G. Alexe, and E. Mândrescu, Strong perfectness of tensor graph product, Rev. Roumaine Math. Pures Appl. 43 (1998), 627--639. MR 1 843 019
E. Olaru and S. Antohe, Algebraische Aspekte der S-Zerlegungen von Graphen. An. Univ. Gala\c ti Metal. 2(7) (1984), 21--26. MR 87f:05133
E. Olaru and E. Mândrescu, On stable transversals and strong perfectness of graph-join, An. Univ. Gala\c ti Metal. 4(9) (1986), 21--24. MR 88i:05083a
E. Olaru and E. Mândrescu, On stable transversals in graphs---an algebraic approach, An. Univ. Gala\c ti Metal. 4(9) (1986), 25--30. MR 88i:05083b
E. Olaru and E. Mândrescu, s-strongly perfect Cartesian product of graphs, J. Graph Theory 16 (1992), 297--303. MR 93i:05109
E. Olaru and H. Sachs, Contributions to a characterization of the structure of perfect graphs, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 121--144. MR 86e:05041
E. Olaru and G. Suciu, Dauerstabile und kritisch imperfekte Graphen, An. Univ. Timi\cedla soara Ser. \cedla Stiin\cedla t. Mat. 17 (1979), 59--64. MR 81f:05082

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
M. W. Padberg, Perfect zero-one matrices, Math. Programming 6 (1974), 180--196. MR 49 #4809
M. W. Padberg, Characterisations of totally unimodular, balanced and perfect matrices, Combinatorial programming: methods and applications (Proc. NATO Advanced Study Inst., Versailles, 1974), NATO Advanced Study Inst. Ser., Ser. C: Math. and Phys. Sci., Vol. 19, Reidel, Dordrecht, 1975, pp. 275--284. MR 53 #10291
M. W. Padberg, Almost integral polyhedra related to certain combinatorial optimization problems, Linear Algebra and Appl. 15 (1976), 69--88. MR 58 #25981
M. W. Padberg, A characterization of perfect matrices, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 169--178. MR 86e:05021
M. W. Padberg, Almost perfect matrices and graphs, Math. Oper. Res. 26 (2001), 1--18. MR 2002e:05063
B.S. Panda and S.P. Mohanty, On some algebraic aspects of Berge's strong perfect graph conjecture, J. Combin. Inform. System Sci. 22 (1997), no. 3-4, 225--232. MR 2000h:05093
K. R. Parthasarathy and G. Ravindra, The strong perfect-graph conjecture is true for K_1,3-free graphs, J. Combinatorial Theory Ser. B 21 (1976), 212--223. MR 55 #10308
K. R. Parthasarathy and G. Ravindra, The validity of the strong perfect-graph conjecture for (K₄-e)-free graphs, J. Combin. Theory Ser. B 26 (1979), 98--100. MR 80m:05045
C. Payan, Perfectness and Dilworth number, Discrete Math. 44 (1983), 229--230. MR 84e:05090
S. G. Penrice, Clique-like dominating sets in perfect graphs, Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995), Congr. Numer. 110 (1995), 77--82. MR 96h:05111
S. Perz and S. Rolewicz, Norms and perfect graphs, Z. Oper. Res. 34 (1990), 13--27. MR 91d:05048
S. Perz and L. S. Zaremba, On a certain subclass of $(\alpha,\omega)$-partitionable graphs, Demonstratio Math. 29 (1996), 377--380. MR 97d:05121
M. Preissmann, A class of strongly perfect graphs, Discrete Math. 54 (1985), 117--120. MR 86g:05038
M. Preissmann, Locally perfect graphs, J. Combin. Theory Ser. B 50 (1990), 22--40. MR 92a:05096
M. Preissmann and D. de Werra, A note on strong perfectness of graphs, Math. Programming 31 (1985), 321--326. MR 86i:05062
M. Preissmann and A. Sebö, Some aspects of minimal imperfect graphs, in: Perfect Graphs (J.L. Ramírez-Alfonsín and B.A. Reed, eds.), Wiley, 2001, pp. 185--214. MR 1 861 363
E. Prisner, Line graphs and generalizations---a survey, Surveys in graph theory (San Francisco, CA, 1995), Congr. Numer. 116 (1996), 193--229. MR 97f:05164
H. J. Prömel and A. Steger, Almost all Berge graphs are perfect, Combin. Probab. Comput. 1 (1992), 53--79. MR 93e:05089
J. Puech, Forbidden graphs and irredundant perfect graphs, J. Combin. Math. Combin. Comput. 36 (2001), 215--228.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
J.L. Ramírez-Alfonsín and B.A. Reed (editors), Perfect Graphs, Wiley, 2001. 392 pp. ISBN: 0-471-48970-0
S. B. Rao and G. Ravindra, A characterization of perfect total graphs, J. Mathematical and Physical Sci. 11 (1977), 25--26. MR 58 #21860
T. Raschle, Generalized Modular Decompositions and the Recognition of Classes of Perfectly Orderable Graphs (electronic), Dissertation, ETH Zürich, 1999.
G. Ravindra, B-graphs, Proceedings of the Symposium on Graph Theory (Indian Statist. Inst., Calcutta, 1976), ISI Lecture Notes, 4, Macmillan of India, New Delhi, 1979, pp. 268--280. MR 80m:05095
G. Ravindra, Meyniel graphs are strongly perfect, J. Combin. Theory Ser. B 33 (1982), 187--190. MR 84f:05062
G. Ravindra, Meyniel's graphs are strongly perfect, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 145--148. MR 87d:05081
G. Ravindra, On Berge's conjecture concerning perfect graphs, Proc. Indian Nat. Sci. Acad. Part A 41 (1975), 294--296. MR 58 #27607
G. Ravindra, Perfectness of normal products of graphs, Discrete Math. 24 (1978), 291--298. MR 80m:05046
G. Ravindra, Strongly perfect line graphs and total graphs, Finite and infinite sets, Vol. I, II (Eger, 1981; A. Hajnal, L. Lovász, and V. T. Sós, eds.), Colloq. Math. Soc. János Bolyai, 37, North-Holland, Amsterdam-New York, 1984, pp. 621--633. MR 87b:05115
G. Ravindra, Perfect graphs, in: Graph theory and its applications (Tirunelveli, 1996), 145--171. Tata McGraw-Hill, New Delhi, 1997. MR 2000d:05052
G. Ravindra, Some classes of strongly perfect graphs, Combinatorics and number theory (Tiruchirappalli, 1996), Discrete Math. 206 (1999), 197--203. MR 2000f:05042
G. Ravindra and D. Basavayya, A characterization of nearly bipartite graphs with strongly perfect complements, J. Ramanujan Math. Soc. 9 (1994), 79--87. MR 95c:05060
G. Ravindra and D. Basavayya, Co-strongly perfect bipartite graphs, J. Math. Phys. Sci. 26 (1992), 321--327. MR 93k:05153
G. Ravindra and D. Basavayya, Co-strongly perfect graphs, J. Math. Phys. Sci. 22 (1988), 439--444.
G. Ravindra and D. Basavayya, Co-strongly perfect line graphs, Combinatorial mathematics and applications (Calcutta, 1988), Sankhy\=a Ser. A 54 (1992), Special Issue, 375--381. MR 94d:05120
G. Ravindra and D. Basavayya, Strongly and costrongly perfect product graphs, J. Math. Phys. Sci. 29 (1995), 71--80. MR 96i:05068
G. Ravindra and K. R. Parthasarathy, Perfect product graphs, Discrete Math. 20 (1977/78), 177--186. MR 58 #10567
B. A. Reed, A note on the semistrong perfect graph conjecture, Discrete Math. 54 (1985), 111--112. MR 86g:05039
B. A. Reed, A semistrong perfect graph theorem, J. Combin. Theory Ser. B 43 (1987), 223--240. MR 88g:05059
B. A. Reed, A note on even pairs, Discrete Math. 65 (1987), 317--318. MR 88f:05066
B. A. Reed, Perfection, parity, planarity and packing paths, Proceedings of IPCO I, University of Waterloo Press, 1990.
B. A. Reed, A gentle introduction to semi-definite programming, in: Perfect Graphs (J.L. Ramírez-Alfonsín and B.A. Reed, eds.), Wiley, 2001, pp. 233--259. MR 1 861 365
B. A. Reed, From a conjecture to a theorem, in: Perfect Graphs (J.L. Ramírez-Alfonsín and B.A. Reed, eds.), Wiley, 2001, pp. 13--24. MR 2002h:05077
B. A. Reed and N. Sbihi, Recognizing bull-free perfect graphs, Graphs Combin. 11 (1995), 171--178. MR 96e:05143
D. J. Rose, Triangulated graphs and the elimination process, J. Math. Anal. Appl. 32 (1970) 597--609. MR 42 #5840
D. J. Rose and R. E. Tarjan, Algorithmic aspects of vertex elimination, Seventh Annual ACM Symposium on Theory of Computing (Albuquerque, N. M., 1975), Assoc. Comput. Mach., New York, 1975, pp. 245--254. MR 56 #7320
D. J. Rose and R. E. Tarjan, Algorithmic aspects of vertex elimination on directed graphs, SIAM J. Appl. Math. 34 (1978), 176--197. MR 58 #8476
D. J. Rose, R. E. Tarjan, and G. S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput. 5 (1976), 266--283. MR 53 #12077
F. Roussel and I. Rusu, Holes and dominoes in Meyniel graphs, Internat. J. Found. Comput. Sci. 10 (1999), 127--146. MR 2001d:05158
F. Roussel and I. Rusu, A linear algorithm to color i-triangulated graphs, Inform. Process. Lett. 70 (1999), 57--62. MR 2000c:05138
F. Roussel, I. Rusu, and H. Thuillier, On graphs with limited number of P₄-partners, Internat. J. Found. Comput. Sci. 10 (1999), 103--121. MR 2000k:05257
I. Rusu, Graphes parfaits: étude structurelle et algorithmes de coloration (electronic), Thèse, Univ.Paris XI, LRI, 1994.
I. Rusu, Perfect and locally perfect colorings, J. Graph Theory 20 (1995), 501--512. MR 96i:05069
I. Rusu, A new class of perfect Hoàng graphs, Discrete Math. 145 (1995), 279--285. MR 96e:05058
I. Rusu, Quasi-parity and perfect graphs, Inform. Process. Lett. 54 (1995), 35--39. MR 96a:05062
I. Rusu, Properly orderable graphs, Discrete Math. 158 (1996), 223--229. MR 97e:05165
I. Rusu, Building counterexamples, Discrete Math. 171 (1997), 213--227. MR 99c:05071
I. Rusu, Berge graphs with chordless cycles of bounded length, J. Graph Theory 32 (1999), 73--79. MR 2000e:05077
I. Rusu, Aspects théoriques et algorithmiques des graphes parfaits (electronic), Habilitation, Univ. d'Orleans, LIFO, 1999.
I. Rusu, P₄-domination in minimal imperfect graphs, Proceedings of the Third International Conference on Graphs and Optimization, GO-III (Leukerbad, 1998), Discrete Appl. Math. 94 (1999), 329--336. MR 2000d:05089
I. Rusu, Berge graphs with chordless cycles of bounded length, J. Graph Theory 32 (1999), 73--79. MR 2000e:05077
I. Rusu, Perfectly contractile diamond-free graphs, J. Graph Theory 32 (1999), 359--389. MR 2001c:05061
I. Rusu, Even pairs in Artemis graphs, Discrete Math. 218 (2000), 185--197. MR 2001k:05088
I. Rusu, Cutsets in perfect and minimal imperfect graphs, in: Perfect Graphs (J.L. Ramírez-Alfonsín and B.A. Reed, eds.), Wiley, 2001, pp. 167--183. MR 1 861 362

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
H. Sachs, On the Berge conjecture concerning perfect graphs, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) Gordon and Breach, New York, 1970, pp. 377--384. MR 42 #7549
M. Saks, A class of perfect graphs associated with planar rectilinear regions, SIAM J. Algebraic Discrete Methods 3 (1982), 330--342. MR 84d:05079
T. Sakuma, A counterexample to the bold conjecture, J. Graph Theory 25 (1997), 165--168. MR 98c:05066
T. Sakuma, Forced color classes, intersection graphs and the strong perfect graph conjecture, Combinatorics and optimization (Okinawa, 1996), Theoret. Comput. Sci. 235 (2000), 309--324. MR 2001k:05079
A. Sassano, Chair-free Berge graphs are perfect, Graphs Combin. 13 (1997), 369--395. MR 98m:05071
A. Sebö, Forcing colorations, and the perfect graph conjecture, Integer Programming and Combinatorial Optimization 2 (E. Balas, G. Cornuéjols, and R. Kannan, eds.), Mathematical Programming Society and Carnegie Mellon University, 1992.
A. Sebö, On critical edges in minimal imperfect graphs, J. Combin. Theory Ser. B 67 (1996), 62--85. MR 97e:05117
A. Sebö, The connectivity of minimal imperfect graphs, J. Graph Theory 23 (1996), 77--85. MR 97h:05108
D. Seinsche, On a property of the class of n-colorable graphs, J. Combinatorial Theory Ser. B 16 (1974), 191--193. MR 49 #2448
P. D. Seymour, On Lehman's width-length characterization, Polyhedral combinatorics (Morristown, NJ, 1989), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 1, Amer. Math. Soc., Providence, RI, 1990, pp. 107--117 MR 92d:05113
C. E. Shannon, The zero error capacity of a noisy channel, Institute of Radio Engineers, Transactions on Information Theory, IT-2, (1956) 8--19. MR 19,623b
J. B. Shearer, A class of perfect graphs, SIAM J. Algebraic Discrete Methods 3 (1982), 281--284. MR 83i:05027
F. B. Shepherd, Near-perfect matrices. Math. Programming 64 (1994), Ser. A, 295--323. MR 95f:05044
F. B. Shepherd, The Theta body and imperfection, in: Perfect Graphs (J.L. Ramírez-Alfonsín and B.A. Reed, eds.), Wiley, 2001, pp. 261--291. MR 2002h:05078
K. Simon, Effiziente Algorithmen für perfekte Graphen, Leitfäden und Monographien der Informatik. B. G. Teubner, Stuttgart, 1992. viii+286 pp. ISBN: 3-519-02940-5 MR 93f:68074
G. Simonyi, Perfect graphs and graph entropy. An updated survey. in: Perfect Graphs (J.L. Ramírez-Alfonsín and B.A. Reed, eds.), Wiley, 2001, pp. 293--328 MR 1 861 367
S. Sorg, Die P₄-Struktur von Kantengraphen bipartiter Graphen, Diploma Thesis, Mathematisches Institut der Universität zu Köln, February 1997.
M. R. Sridharan and O. T. George, On the strong perfect graph conjecture and critical graphs, Discrete Math. 41 (1982), 101--104. MR 84b:05080
L. Sun, Two classes of perfect graphs, J. Combin. Theory Ser. B 53 (1991), 273--292. MR 92j:05075
L. Surányi, The covering of graphs by cliques, Studia Sci. Math. Hungar. 3 (1968) 345--349. MR 38 #76
A. Szelecka and A. Wloch, A note on strong and co-strong perfectness of the X-join of graphs, Discuss. Math. Graph Theory 16 (1996), 151--155. MR 98e:05047

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A. Tamura, Perfect (0,±1)-matrices and perfect bidirected graphs, Combinatorics and optimization (Okinawa, 1996), Theoret. Comput. Sci. 235 (2000), 339--356.MR 2001i:15019
R. E. Tarjan, Decomposition by clique separators, Discrete Math. 55 (1985), 221--232. MR 87i:05134
R. E. Tarjan and M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput. 13 (1984), 566--579. MR 86f:68017a. Addendum: SIAM J. Comput. 14 (1985), 254--255. MR 86f:68017b
A. Thomas, A class of perfect graphs in genetics, IMA J. Math. Appl. Med. Biol. 10 (1993), 77--81. CMP 1 234 554
B. Toft, Colouring, stable sets and perfect graphs, Handbook of combinatorics, Vol. 1, 2, Elsevier, Amsterdam, 1995, pp. 233--288. MR 97d:05123
I. Tomescu, Sur le nombre des cliques maximales d'un graphe et quelques problèmes sur les graphes parfaits, Rev. Roumaine Math. Pures Appl. 16 (1971), 1115--1126. MR 45 #103
L. E. Trotter, Jr., A class of facet producing graphs for vertex packing polyhedra, Discrete Math. 12 (1975), 373--388. MR 53 #2759
L. E. Trotter, Jr., Line perfect graphs, Math. Programming 12 (1977), 255--259. MR 56 #15501
A. Tucker, The strong perfect graph conjecture and an application to a municipal routing problem, Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Lecture Notes in Math., Vol. 303, Springer, Berlin, 1972, pp. 297--303. MR 49 #7181
A. Tucker, Perfect graphs and an application to optimizing municipal services, SIAM Rev. 15 (1973), 585--590. MR 48 #3817
A. Tucker, The strong perfect graph conjecture for planar graphs, Canad. J. Math. 25 (1973), 103--114. MR 47 #4868
A. Tucker, Coloring a family of circular arcs, SIAM J. Appl. Math. 29 (1975), 493--502. MR 55 #10309
A. Tucker, Critical perfect graphs and perfect 3-chromatic graphs, J. Combinatorial Theory Ser. B 23 (1977), 143--149. MR 58 #16369
A. Tucker, Berge's strong perfect graph conjecture, Second International Conference on Combinatorial Mathematics (New York, 1978), Ann. New York Acad. Sci., 319, New York Acad. Sci., New York, 1979, pp. 530--535. MR 81c:05041
A. Tucker, Coloring graphs with stable cutsets, J. Combin. Theory Ser. B 34 (1983), 258--267. MR 85d:05120
A. Tucker, Uniquely colorable perfect graphs, Discrete Math. 44 (1983), 187--194. MR 84k:05047
A. Tucker, The validity of the perfect graph conjecture for K₄-free graphs, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 149--157. MR 86j:05067
A. Tucker, A reduction procedure for coloring perfect K₄-free graphs, J. Combin. Theory Ser. B 43 (1987), 151--172. MR 88k:05085
A. Tucker, Coloring perfect (K₄-e)-free graphs, J. Combin. Theory Ser. B 42 (1987), 313--318. MR 88f:05047
A. Tucker and D. Wilson, An O(n²) algorithm for coloring perfect planar graphs, J. Algorithms 5 (1984), 60--68. MR 85f:68039
Zs. Tuza, Perfect graph decompositions, Graphs Combin. 7 (1991), 89--93. MR 92d:05076
Zs. Tuza, Perfect triangle families, Bull. London Math. Soc. 26 (1994), 321--324. MR 96b:05083

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A. Wagler, Critical edges in perfect line graphs and some polyhedral consequences, Proceedings of the Conference on Optimal Discrete Structures and Algorithms---ODSA '97 (Rostock), Discrete Appl. Math. 95 (1999), 455--466. MR 2000e:05078
A. Wagler, On critically perfect graphs, J. Graph Theory 32 (1999), 394--404. MR 2000k:05123
W. D. Wallis and J. L. Wu, Squares, clique graphs and chordality, J. Graph Theory 20 (1995), 37--45. MR 96g:05120
J. R. Walter, Representations of chordal graphs as subtrees of a tree, J. Graph Theory 2 (1978), 265--267. MR 58 #21868
C. Wang, Modular threshold graphs are perfect, Combinatorics and graph theory '95, Vol. 1 (Hefei), World Sci. Publishing, River Edge, NJ, 1995, pp. 388--397. MR 98f:05068
V. K. Wei, A connection between a convex programming problem and the LYM property on perfect graphs, J. Graph Theory 12 (1988), 571--587. MR 90b:05115
D. de Werra, On line-perfect graphs, Math. Programming 15 (1978), 236--238. MR 81a:05052
D. de Werra and A. Hertz, On perfectness of sums of graphs, Discrete Math. 195 (1999), 93--101. MR 2000c:05072
W. Wessel, Some color-critical equivalents of the strong perfect graph conjecture, Contributions to graph theory and its applications (Internat. Colloq., Oberhof, 1977) (German), Tech. Hochschule Ilmenau, Ilmenau, 1977, pp. 300--309. MR 82h:05033
S. H. Whitesides, A classification of certain graphs with minimal imperfection properties, Discrete Math. 38 (1982), 303--310. MR 84a:05029
S. H. Whitesides, A classification of certain graphs with minimal imperfection properties, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 207--218. MR 86i:05090
S. H. Whitesides, A method for solving certain graph recognition and optimization problems, with applications to perfect graphs, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 281--297. MR 86i:05091
S. H. Whitesides, An algorithm for finding clique cut-sets, Inform. Process. Lett. 12 (1981), 31--32. MR 82a:68133
A. Wloch, k-strongly perfect products of graphs, Zeszyty Nauk. Politech. Rzeszowskiej Mat. (1995), 109--113. MR 97h:05156

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Q. Xue, (C₄, Lotus)-free Berge graphs are perfect, An. \c Stiin\c t. Univ. Al. I. Cuza Ia\c si Inform. (N.S.) 4 (1995), 65--71 (1996). MR 97f:05166
Q. Xue, On a class of square-free graphs, Inform. Process. Lett. 57 (1996), 47--48. MR 96k:05169

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
L. S. Zaremba, Perfect graphs and norms, Math. Programming 51 (1991), (Ser. A), 269--272. MR 92m:05162
L. S. Zaremba and S. Perz, On a geometric property of perfect graphs, Combinatorica 2 (1982), 395--397. MR 85b:05150
A. Zemirline, Quasi-star-cutsets and some consequences, Graphs and scheduling (Bendor, 1999). European J. Oper. Res. 137 (2002), 326--335. MR 1 881 479
Z. F. Zhang, X. Z. Lü, Z. G. Wang, and X. J. Shen, Strong perfectness of total graphs. (Chinese) J. Math. Res. Exposition 14 (1994), 621--624. MR 95j:05100
B. Zhou, Some theorems concerning the star chromatic number of a graph, J. Combin. Theory Ser. B 70 (1997), 245--258. MR 99b:05069

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z