. Vi, A graph G is perfect if and only if G and G are 2-divisible

]. G. Bacsó, E. Boros, V. Gurvich, F. Maray, and M. Preissmann, On minimal imperfect graphs with circular symmetry, Journal of Graph Theory, vol.29, issue.4, pp.209-225, 1998.
DOI : 10.1002/(SICI)1097-0118(199812)29:4<209::AID-JGT1>3.3.CO;2-M

C. Berge, Les problèmes de coloration en théorie des graphes, Publ, Inst. Stat. Univ. Paris, vol.9, 1960.

M. E. Bertschi and B. A. Reed, Erratum: A note on even pairs [Discrete Math, pp.317-318, 1987.

R. E. Bixby, A Composition for Perfect Graphs, Topics on Perfect Graphs, pp.221-224, 1984.
DOI : 10.1016/S0304-0208(08)72937-2

R. G. Bland, H. Huang, and L. E. Trotter-jr, Graphical properties related to minimal imperfection, Discrete Math, pp.11-22, 1979.

E. Boros, V. A. Gurvich, and S. Hougardy, Recursive generation of partitionable graphs, Journal of Graph Theory, vol.21, issue.4, pp.259-285, 2002.
DOI : 10.1002/jgt.10067

M. Burlet and J. Fonlupt, Polynomial algorithm to recognize a Meyniel graph, Topics on Perfect Graphs, pp.225-252, 1984.

M. Burlet and J. P. Uhry, Parity graphs, Topics on Perfect Graphs, pp.253-278, 1984.
URL : https://hal.archives-ouvertes.fr/tel-00294963

K. Cameron, Polyhedral and algorithmic ramications of antichains, 1982.

M. Chudnovsky and . Berge-trigraphs, Berge trigraphs, Journal of Graph Theory, vol.83, issue.1, pp.1-55, 2006.
DOI : 10.1002/jgt.20165

M. Chudnovsky, Berge Trigraphs and Their Applications, 2003.

M. Chudnovsky, G. Cornuéjols, X. Liu, P. Seymour, and K. Vu²kovi¢, Recognizing Berge Graphs, Combinatorica, vol.25, issue.2, pp.143-186, 2005.
DOI : 10.1007/s00493-005-0012-8

M. Chudnovsky, N. Robertson, P. D. Seymour, and R. Thomas, The strong perfect graph theorem, Annals of Mathematics, vol.164, issue.1, pp.51-229, 2006.
DOI : 10.4007/annals.2006.164.51

V. Chvátal, R. L. Graham, A. F. Perold, and S. H. Whitesides, Combinatorial designs related to the strong perfect graph conjecture, Discrete Mathematics, vol.26, issue.2, pp.83-92, 1979.
DOI : 10.1016/0012-365X(79)90114-6

V. Chvátal and N. Sbihi, Bull-free Berge graphs are perfect, Graphs Combin, pp.127-139, 1987.

V. Chvátal and N. Sbihi, Recognizing claw-free perfect graphs, Journal of Combinatorial Theory, Series B, vol.44, issue.2, pp.154-176, 1988.
DOI : 10.1016/0095-8956(88)90085-8

M. Conforti and G. Cornuéjols, Graphs without odd holes, parachutes or proper wheels: a generalization of Meyniel graphs and of line graphs of bipartite graphs, Journal of Combinatorial Theory, Series B, vol.87, issue.2, pp.300-330, 2003.
DOI : 10.1016/S0095-8956(02)00021-7

M. Conforti, G. Cornuéjols, G. Gasparyan, and K. , Perfect Graphs, Partitionable Graphs and Cutsets, Combinatorica, vol.22, issue.1, pp.19-33, 2002.
DOI : 10.1007/s004930200001

M. Conforti, G. Cornuéjols, A. Kapor, and K. Vu²kovi¢, Balanced 0,????1 Matrices I. Decomposition, Journal of Combinatorial Theory, Series B, vol.81, issue.2, pp.243-306, 2001.
DOI : 10.1006/jctb.2000.2010

M. Conforti, G. Cornuéjols, A. Kapor, and K. Vu²kovi¢, Even-hole-free graphs part I: Decomposition theorem, Journal of Graph Theory, vol.32, issue.1, pp.6-49, 2002.
DOI : 10.1002/jgt.10006

M. Conforti, G. Cornuéjols, A. Kapor, and K. Vu²kovi¢, Even-hole-free graphs part II: Recognition algorithm, Journal of Graph Theory, vol.67, issue.4, pp.238-266, 2002.
DOI : 10.1002/jgt.10045

M. Conforti, G. Cornuéjols, X. Liu, K. Vu²kovi¢, and G. Zambelli, Odd Hole Recognition in Graphs of Bounded Clique Size, SIAM Journal on Discrete Mathematics, vol.20, issue.1, pp.42-48, 2006.
DOI : 10.1137/S089548010444540X

M. Conforti, G. Cornuéjols, and M. R. Rao, Decomposition of Balanced Matrices, Journal of Combinatorial Theory, Series B, vol.77, issue.2, pp.292-496, 1999.
DOI : 10.1006/jctb.1999.1932

M. Conforti, G. Cornuéjols, and K. Vu²kovi¢, Square-free perfect graphs, Journal of Combinatorial Theory, Series B, vol.90, issue.2, pp.257-307, 2004.
DOI : 10.1016/j.jctb.2003.08.003

M. Conforti and M. R. Rao, Testing balancedness and perfection of linear matrices, Mathematical Programming, vol.10, issue.1-3, pp.61-62, 1993.
DOI : 10.1007/BF01582135

D. G. Corneil and J. Fonlupt, Stable Set Bonding in Perfect Graphs and Parity Graphs, Journal of Combinatorial Theory, Series B, vol.59, issue.1, pp.1-14, 1993.
DOI : 10.1006/jctb.1993.1049

G. Cornuéjols, Combinatorial Optimization: Packing and Covering, CBMS-NSF Regional Conference Series in Applied Mathematics 74, 2001.
DOI : 10.1137/1.9780898717105

G. Cornuéjols and B. Cunningham, Compositions for perfect graphs, Discrete Math, pp.245-254, 1985.

G. Cornuéjols and B. A. Reed, Complete Multi-partite Cutsets in Minimal Imperfect Graphs, Journal of Combinatorial Theory, Series B, vol.59, issue.2, pp.191-198, 1993.
DOI : 10.1006/jctb.1993.1065

G. Cornuéjols, X. Liu, and K. , Vu²kovi¢ -A polynomial algorithm for recognizing perfect graphs, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp.20-27, 2003.

W. H. Cunningham, Decomposition of Directed Graphs, SIAM Journal on Algebraic Discrete Methods, vol.3, issue.2, pp.214-228, 1982.
DOI : 10.1137/0603021

G. A. Dirac, On rigid circuit graphs, Abhandlungen aus dem Mathematischen Seminar der Universit??t Hamburg, vol.13, issue.1-2, pp.71-76, 1961.
DOI : 10.1007/BF02992776

J. Edmonds, Paths, trees, and flowers, Journal canadien de math??matiques, vol.17, issue.0, pp.449-467, 1965.
DOI : 10.4153/CJM-1965-045-4

J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices, Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, vol.69, issue.1 and 2, pp.125-130, 1965.
DOI : 10.6028/jres.069B.013

J. Edmonds and R. Giles, A Min-Max Relation for Submodular Functions on Graphs, Ann. Discrete Math, vol.1, pp.185-204, 1977.
DOI : 10.1016/S0167-5060(08)70734-9

C. M. De-figueiredo, S. Klein, Y. Kohayakawa, and B. A. Reed, Finding Skew Partitions Efficiently, Journal of Algorithms, vol.37, issue.2, pp.505-521, 2000.
DOI : 10.1006/jagm.1999.1122

J. Fonlupt and A. Seb®, On the clique rank and the coloration of perfect graphs, pp.201-229, 1990.

J. Fonlupt and J. Uhry, Transformations which Preserve Perfectness and H-Perfectness of Graphs, Bonn Workshop on Combinatorial Optimization Ann. Discrete Math, vol.16, pp.83-95, 1980.
DOI : 10.1016/S0304-0208(08)72445-9

J. Fonlupt and A. Zemirline, A polynomial algorithm for recognizing K 4 ? e-free perfect graphs, Rev. Maghrébine Math, vol.2, pp.1-26, 1993.

D. R. Fulkerson, Anti-blocking polyhedra, Journal of Combinatorial Theory, Series B, vol.12, issue.1, pp.50-71, 1972.
DOI : 10.1016/0095-8956(72)90032-9

G. S. Gasparyan, Minimal imperfect graphs: A simple approach, Combinatorica, vol.6, issue.2, pp.209-212, 1996.
DOI : 10.1007/BF01844846

F. Gavril, Algorithms on clique separable graphs, Discrete Mathematics, vol.19, issue.2, pp.159-165, 1977.
DOI : 10.1016/0012-365X(77)90030-9

C. Grinstead, On circular critical graphs, Discrete Math, pp.11-24, 1984.

M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, vol.2, issue.2, pp.169-197, 1981.
DOI : 10.1007/BF02579273

M. Grötschel, L. Lovász, and A. Schrijver, Polynomial Algorithms for Perfect Graphs, Topics on Perfect Graphs, pp.325-356, 1984.
DOI : 10.1016/S0304-0208(08)72943-8

M. Grötschel, L. Lovász, and A. Schrijver, Relaxations of vertex packing, Journal of Combinatorial Theory, Series B, vol.40, issue.3, pp.330-343, 1986.
DOI : 10.1016/0095-8956(86)90087-0

M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, 1988.

V. A. Gurvich and V. Udalov, Berge strong perfect graph conjecture holds for the graphs with less than 25 vertices, manuscript, 1992.

A. Gyárfás, Problems from the world surrounding perfect graphs, Proceedings of the International Conference on Combinatorial Analysis and its Applications, pp.413-441, 1987.

R. Hayward, Weakly triangulated graphs, Journal of Combinatorial Theory, Series B, vol.39, issue.3, pp.200-208, 1985.
DOI : 10.1016/0095-8956(85)90050-4

C. T. Hoàng, Some properties of minimal imperfect graphs, Discrete Math, pp.165-175, 1996.

C. T. Hoàng and C. Mcdiarmid, On the divisibility of graphs, Discrete Math, pp.145-156, 2002.

S. Hougardy, Counterexamples to three conjectures concerning perfect graphs, Discrete Mathematics, vol.117, issue.1-3, 1991.
DOI : 10.1016/0012-365X(93)90338-T

S. Hougardy, Even pairs and the strong perfect graph conjecture, Discrete Math, pp.277-278, 1996.

W. Hsu, Decomposition of perfect graphs, Journal of Combinatorial Theory, Series B, vol.43, issue.1, pp.70-94, 1987.
DOI : 10.1016/0095-8956(87)90031-1

W. Hsu, Recognizing planar perfect graphs, Journal of the ACM, vol.34, issue.2, pp.255-288, 1987.
DOI : 10.1145/23005.31330

K. Jansen, A new characterization for parity graphs and a coloring problem with costs, Lecture Notes in Computer Science, vol.1380, pp.249-260, 1998.
DOI : 10.1007/BFb0054326

L. Lovász, A characterization of perfect graphs, Journal of Combinatorial Theory, Series B, vol.13, issue.2, pp.95-98, 1972.
DOI : 10.1016/0095-8956(72)90045-7

L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math, pp.253-267, 1972.

L. Lovász, On the Shannon capacity of a graph, IEEE Transactions on Information Theory, vol.25, issue.1, pp.1-7, 1979.
DOI : 10.1109/TIT.1979.1055985

L. Lovász and A. Schrijver, Cones of Matrices and Set-Functions and 0???1 Optimization, SIAM Journal on Optimization, vol.1, issue.2, pp.166-190, 1991.
DOI : 10.1137/0801013

F. Maray and M. Preissmann, Split neighbourhood graphs and the strong perfect graph conjecture, J. Combin. Theory Ser. B, vol.63, pp.294-309, 1995.

F. Maray and M. Preissmann, Perfect graphs with no P 5 and K 5 , Graphs Combin, pp.179-184, 1994.

S. E. Markosyan and I. A. Karapetyan, ?-Perfect graphs, Cybernetics, vol.13, issue.No. 5, pp.292-296, 1976.
DOI : 10.1007/BF01068603

M. W. Padberg, Perfect zero???one matrices, Mathematical Programming, vol.5, issue.1, pp.180-196, 1974.
DOI : 10.1007/BF01580235

URL : https://hal.archives-ouvertes.fr/inria-00076517

M. W. Padberg, Almost integral polyhedra related to certain combinatorial optimization problems, Linear Algebra and Appl, pp.69-88, 1976.

C. H. Papadimitriou and M. Yannakakis, On recognizing integer polyhedra, Combinatorica, vol.10, issue.1, pp.107-109, 1990.
DOI : 10.1007/BF02122701

K. R. Parthasarathy and G. Ravindra, The strong perfect-graph conjecture is true for K1,3-free graphs, Journal of Combinatorial Theory, Series B, vol.21, issue.3, pp.212-223, 1976.
DOI : 10.1016/S0095-8956(76)80005-6

K. R. Parthasarathy and G. Ravindra, The validity of the strong perfect-graph conjecture for (K4???e)-free graphs, Journal of Combinatorial Theory, Series B, vol.26, issue.1, pp.98-100, 1979.
DOI : 10.1016/0095-8956(79)90047-9

A. Pêcher, Graphes de cayley partitionnables, 2000.

M. Preissmann and A. Seb®, Some aspects of minimal imperfect graphs, pp.185-214, 2001.

B. A. Reed, A semi-strong Perfect Graph theorem, Journal of Combinatorial Theory, Series B, vol.43, issue.2, 1986.
DOI : 10.1016/0095-8956(87)90022-0

F. Roussel, . Ph, and . Rubio, About Skew Partitions in Minimal Imperfect Graphs, Journal of Combinatorial Theory, Series B, vol.83, issue.2, pp.171-190, 2001.
DOI : 10.1006/jctb.2001.2044

F. Roussel and I. Rusu, HOLES AND DOMINOES IN MEYNIEL GRAPHS, International Journal of Foundations of Computer Science, vol.10, issue.02, pp.127-146, 1999.
DOI : 10.1142/S0129054199000113

URL : https://hal.archives-ouvertes.fr/hal-00442411

I. Rusu, Building counterexamples, Discrete Math, pp.213-227, 1997.

I. Rusu, Cutsets in perfect and minimal imperfect graphs, pp.167-183, 2001.

H. Sachs, On the Berge conjecture concerning perfect graphs, Combinatorial structures and their applications, pp.377-384, 1969.

T. Sakuma, A counterexample to the bold conjecture, Journal of Graph Theory, vol.25, issue.2, pp.165-168, 1997.
DOI : 10.1002/(SICI)1097-0118(199706)25:2<165::AID-JGT8>3.0.CO;2-K

A. Sassano, Chair-free Berge graphs are perfect, Graphs Combin, pp.369-395, 1997.

A. Schrijver, Polyhedral combinatorics, Handbook of Combinatorics, pp.1650-1704, 1995.

A. Seb®, On Critical Edges in Minimal Imperfect Graphs, Journal of Combinatorial Theory, Series B, vol.67, issue.1, pp.62-85, 1996.
DOI : 10.1006/jctb.1996.0034

A. Sebho, Forcing colorations and the strong perfect graph conjecture, Integer Programming and Combinatorial Optimization II, pp.431-445, 1992.

A. Seb®, The connectivity of minimal imperfect graphs, Journal of Graph Theory, vol.23, issue.1, pp.77-85, 1996.
DOI : 10.1002/(SICI)1097-0118(199609)23:1<77::AID-JGT9>3.0.CO;2-H

D. Seinsche, On a property of the class of n-colorable graphs, Journal of Combinatorial Theory, Series B, vol.16, issue.2, pp.191-193, 1974.
DOI : 10.1016/0095-8956(74)90063-X

P. Seymour, Decomposition of regular matroids, Journal of Combinatorial Theory, Series B, vol.28, issue.3, pp.305-359, 1980.
DOI : 10.1016/0095-8956(80)90075-1

P. Seymour, How the proof of the strong perfect graph conjecture was found

F. B. Shepherd, Near-perfect matrices, Mathematical Programming, vol.23, issue.1-3, pp.295-323, 1994.
DOI : 10.1007/BF01582578

F. B. Shepherd, The Theta Body and Imperfection, pp.261-291, 2001.

A. Tucker, Critical perfect graphs and perfect 3-chromatic graphs, Journal of Combinatorial Theory, Series B, vol.23, issue.1, pp.313-318, 1977.
DOI : 10.1016/0095-8956(77)90064-8

A. Tucker, BERGE'S STRONG PERFECT GRAPH CONJECTURE, Annals of the New York Academy of Sciences, vol.21, issue.1 Second Intern, pp.530-535, 1979.
DOI : 10.1137/0129040

A. Tucker, Uniquely colorable perfect graphs, Discrete Math, pp.187-194, 1983.

A. Tucker, Coloring graphs with stable cutsets, Journal of Combinatorial Theory, Series B, vol.34, issue.3, pp.258-267, 1983.
DOI : 10.1016/0095-8956(83)90039-4

A. Tucker, Coloring perfect (K4 ??? e)-free graphs, Journal of Combinatorial Theory, Series B, vol.42, issue.3, pp.313-318, 1987.
DOI : 10.1016/0095-8956(87)90048-7

A. Wagler, Rank-perfect and weakly rank-perfect graphs, ZIB-Report 01, pp.1-27, 2001.

A. Wagler, Relaxing perfectness: which graphs are "almost" perfect?, ZIB-Report 02-03, pp.1-24, 2003.

S. H. Whitesides, A Method for Solving Certain Graph Recognition and Optimization Problems, with Applications to Perfect Graphs, Topics on Perfect Graphs, pp.281-297, 1984.
DOI : 10.1016/S0304-0208(08)72941-4

G. Zambelli, On Perfect Graphs and Balanced Matrices, 2004.