{'fraction_non_alphanumeric': 0.04662441872079731, 'fraction_numerical': 0.013895208816576585, 'mean_word_length': 3.7076280041797283, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 59, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Perfect graphs: a survey

Perfect graphs were defined by Claude Berge in the 1960s. They are important objects for graph theory, linear programming and combinatorial optimization. Claude Berge made a conjecture about them, that was proved by Chudnovsky, Robertson, Seymour and Thomas in 2002, and is now called the strong perfect graph theorem. This is a survey about perfect graphs, mostly focused on the strong perfect graph theorem.


Introduction
The chromatic number of a graph G, denoted by χ(G), is the minimum number of colours needed to assign a colour to each vertex of G in such a way that adjacent vertices receive different colours. The clique number of G, denoted by ω(G) is the maximum number of pairwise adjacent vertices in G. Every graph G clearly satisfies χ(G) ≥ ω(G), because the vertices of a clique must receive different colours. A graph G is perfect if every induced subgraph H of G satisfies χ(H) = ω(H). A chordless cycle of length 2k + 1, k ≥ 2, satisfies 3 = χ > ω = 2, and its complement satisfies k + 1 = χ > ω = k. These graphs are therefore imperfect. Since perfect graphs are closed under taking induced subgraphs, they must be defined by excluding a familly F of graphs as induced subgraphs. The strong perfect graph theorem (SPGT for short) states that the two examples that we just gave are the only members of F.
Let us make this more formal. A hole in a graph G is an induced subgraph of G isomorphic to a cycle chordless cycle of length at least 4. An antihole is an induced subgraph H of G, such that H is hole of G. A hole (resp. an antihole) is odd or even according to the number of its vertices (that is equal to the number of its edges). A graph is Berge if it does not contain an odd hole nor an odd antihole. The following, known as the SPGT, was conjectured by Berge [5] in the 1960s and was the object of much research until it was finally proved in 2002 by Chudnovsky, Robertson, Seymour and Thomas [20] (since then, a shorter proof was discovered by Chudnovsky and Seymour [24]). One direction is easy: every perfect graph is Berge, since as we observed already odd holes and antiholes satisfy χ = ω + 1. The proof of the converse is very long and relies on structural graph theory. The main step is a decomposition theorem (Theorem 6.1), stating that every Berge graph is either in a well-understood basic class of perfect graphs (see Section 3), or has some decomposition (see Section 4). The goal of this survey is to make this result and its meaning understandable to a non-specializist mathematician. To this purpose, not only the proof is surveyed, but also results that were seminal to it, and some that were proved after it. Our goal is also to present perfect graphs as a lively subject for researchers, by mentioning several attractive open questions at the end of the coming sections. Putting forward up to date open questions is useful, because the proof of the SPGT somehow took back the motivation for many questions, in particular about classes of perfect graphs whose study was supposed to give insight about the big open question.
Let us start now with an open question that obviously has the same flavour as the SPGT. Gyárfás [53] proposed the following generalization of perfect graphs. A graph is χ-bounded by a function f if every induced subgraph H of G satisfies χ(H) ≤ f (ω(H)). Hence, perfect graphs are χbounded by the identity function. There might exist a short proof that for some function f (possibly fast increasing), all Berge graphs are χ-bounded by f , but so far, the proof of the SPGT is the only known proof of this fact. In [53] the following conjecture is stated. It is still open, but several attempts led to beautiful results, such as Scott [91] and Chudnovsky, Robertson, Seymour and Thomas [21]. Conjecture 1.2 (Gyárfás 1987) There exists a function f such that for all graphs G, if G has no odd hole, then G is χ-bounded by f .

Terminology
By the SPGT, perfect graphs and Berge graphs form the same class. Still, we use Berge when we mostly rely on excluding holes and antiholes, and perfect when we mostly rely on colourings. Anyway, this distinction has to be kept when we sketch the proof of the SPGT. A minimally imperfect graph is an imperfect graph every proper induced subgraph of which is perfect. A restatement of the SPGT is that minimally imperfect graphs are precisely the odd holes and antiholes. Many statements about minimal imperfect graphs are therefore trivial to check by using the SPGT, but when proving the SPGT, it is essential to prove them by other means. Observe that a minimal (or minimum) counter-example to the SPGT has to be a Berge minimally imperfect graph.
We mostly follow the terminology from [20] that is sometimes not fully standard. Since all this theory deals with induced subgraphs, we write G contains H to mean that H is an induced subgraph of G. We simply write path instead of chordless path or induced path. When a and b are vertices of a path P , we denote by aP b the subpath of P whose ends are a and b. A subset A of V (G) is complete to a subset B of V (G) if A and B are disjoint and every vertex of A is adjacent to every vertex of B (we also say that B is A-complete).
We use the prefix anti to mean a property or a structure of the complement (like in holes and antiholes). For instance, an antipath in G is a path in G; A is anticomplete to B means that no edge of G has an end in A and the other one in B; a graph G is anticonnected if its complement is connected. By C(A) we mean the set of all A-complete vertices in G and by C(A) the set of all A-anticomplete vertices.
By colouring of a graph, we mean an optimal colouring of the vertices.

Further reading
Since we focus on the SPGT and its proof, most of this survey is on the structure of Berge graphs, and we omit many other important (more important?) aspects of the theory of perfect graphs, such as the ellipsoïd method used by Gröstchel, Lovász and Schrijver [52] to colour in polynomial time any input perfect graph. The theory of semi-definite programming started there. Several previous surveys exist (and we try not to overlap them too much). As far as we know, all of them were written before of just after the proof of the SPGT. The survey of Lovász [70] from the 1980s is still a good reading. Two books are completely devoted to perfect graphs [7,83], and contain a lot of material that will be cited in what follows. Part VI of the treatise of Schrijver [90] is a good survey on perfect graphs (it is the most comprehensive). Chudnovsky, Robertson, Seymour and Thomas [19] wrote a good survey just after their proof. Roussel, Rusu and Thuillier [87] wrote a good survey about the long sequence of results, attempts and conjectures that finally led to the successful approach.
About more historical aspects, see Section 67.4g in Schrijver [90]. Berge and Ramírez Alfonsín [6] wrote an article about the origin of perfect graphs. Seymour [92] wrote an article, that is interesting even to a nonmathematician, telling the story of how the SPGT was proved.

Lovász's perfect graph theorem
As pointed out by Preissmann and Sebő [81], the following conveniently gives a weak (ii) and a strong (iii) characterization of perfect graphs. Hence, to prove perfection, checking the weak one is enough, while to use perfection, one may rely on the strong one. This allows a kind of leverage that is used a lot in the sequel. Lemma 2.1 (Folklore) Let G be a graph. The three statements below are equivalent.
(i) G is perfect.
(ii) For every induced subgraph H of G and every v ∈ V (H), H contains a stable set that contains v and intersects all maximum cliques of H.
(iii) For every induced subgraph H of G, H contains a stable set that intersects all maximum cliques of H.
Proof. To prove that (i) implies (ii), consider an optimal colouring of H and the colour class S that contains v. So S is a stable set, and it must intersect all maximum cliques of H for otherwise χ(H \ S) ≥ ω(H), a contradiction. Trivially, (ii) implies (iii). To prove that (iii) implies (i), consider the following greedy colouring algorithm: (step 1) set i ← 1 and H ← G; (step 2) while H is non-empty, consider a stable set of H as in (iii), give it colour i, and set H ← H \ S, i ← i + 1. Since ω decreases at each step, this algorithm produces a colouring of G with ω(G) colours, and it can be processed for any induced subgraph of G. Thus, G is perfect. Replicating a vertex v of a graph G means adding a new vertex v adjacent to v and all neighbors of v. As an example, consider the (non-perfect) graph G obtained by replicating one vertex of C 5 . Clearly, χ(G) = ω(G) = 3 (see Fig. 2). However, by replicating any vertex of degree 2 in G, a graph G such that χ(G ) = 4 > ω(G ) = 3 is obtained. This shows that the property χ = ω is not preserved by replication. Therefore, the following lemma due to Lovász [69,71] and known as the replication lemma is more surprising than it may look at first glance. Lemma 2.2 ) Perfection is preserved by replication.
Proof. Let G be a perfect graph and G a graph obtained from G by replicating a vertex v. We show that G satisfies the characterization (iii) from Lemma 2.1. Let H be an induced subgraph of G . We look for a stable set S that intersects all maximum cliques of H. If H contains at most one vertex from {v, v }, then it is isomorphic to a an induced subgraph of G, so clearly S exists. Otherwise, H \ v is perfect, so, by charactization (ii), there exists a stable set S that contains v and intersects all maximum cliques of H \ v . In fact S intersects all maximum cliques of H, because a maximum clique of H contains v if and only if it contains v .
The following was conjectured by Berge as the weak perfect graph conjecture and is now called the perfect graph theorem. We give the proof that, among the available ones, we feel the most related to the rest of this survey. The stable set number of a graph G, denoted by α(G), is the maximum number of pairwise non-adjacent vertices. Observe that for all graphs G, α(G) = ω(G). Theorem 2.3 ) If a graph is perfect, then its complement is perfect.
Proof. Let G be a perfect graph. Construct G as follows: start from G and replicate α v − 1 times every vertex v, where α v is the number of maximum stables sets of G that contain v. Note that replicating −1 time means deleting the vertex, and replicating 0 times means doing nothing. From its construction, G can be covered by k disjoint maximum stable sets, that therefore form an optimal colouring of G . Since G is perfect by Lemma 2.2, if follows that G has a clique K of size k. Since a clique and a stable set intersect in at most one vertex, K intersect all maximum stable sets of G . Now construct a clique K of G, by taking for each vertex of K the vertex of G it is replicated from. The clique K that we obtain intersects all maximum stable sets of G. By the same lines, a clique intersecting all maximum stable sets can be found in any induced subgraph of G. Hence the complement of G satisfies condition (iii) of Lemma 2.1 and is therefore perfect.
In [53], the question of generalizing Theorem 2.3 is discussed. Since [53], hardly any progress occurred in this direction. In particular the following neat generalization of Theorem 2.3 is still open.
Conjecture 2.4 (Gyárfás 1987) There exists a function f such that for all graphs G, if G is χ-bounded by x → x + 1, then its complement is χbounded by f .

Further reading
The perfect graph theorem has a polyhedral proof found by Fulkerson [47] related to polyhedral characterizations of perfect graphs discovered by Fulkerson [47] and Chvátal [29]. Lovász [68] proved a deep characterization of perfect graphs suggested by Hajnal: a graph G is perfect if and only if every induced subgraph H of G satisfies α(H)ω(H) ≥ |V (H)| (this can be proved by a simple argument relying on linear algebra discovered by Gasparian [50], see also [40,10], and Section 12 below for applications of linear algebraic methods to perfect graphs). This characterization implies that deciding the perfection of an input graph is a CoNP problem (see [81] for more about that). Since the characterization is self-complementary, it gives another proof of the perfect graph theorem. This characterization is the starting point of many developments of great signifiance, such as the theory of partitionable graphs (see the survey of Preissmann and Sebő [81]). It has deep connections with combinatorial optimization as explained in a book of Cornuéjols [36].

Basic graphs
In this section, we survey the five basic classes that are used in the proof of the SPGT. We denote by θ(G) the chromatic number of G, by ν(G) the maximum size of a matching in G, by ∆(G) the maximum degree of a vertex in G, by τ (G) the minimum number of edges of G needed to cover all vertices of G, and by χ (G) the minimum number of colours needed to assign a colour to each edge of G in such a way that adjacent edges receive different colours. Bipartite graphs are easily checked to be perfect. So, by Theorem 2.3, their complements are also perfect, which can be restated as 'every bipartite graph G satisfies θ(G) = α(G)'. Since for any trianglefree graph G, |V (G)| = θ(G) + ν(G) = α(G) + τ (G), we obtain that every bipartite graph G satisfies ν(G) = τ (G). This can be rephrased as: 'the complements of line graphs of bipartite graphs are perfect'. By applying again Theorem 2.3, we obtain that line graphs of bipartite graphs are perfect, which can be restated as 'every bipartite graph G satisfies ∆(G) = χ (G)'. Hence, Theorem 2.3 implies the perfection of three among the four historical basic classes of perfect graphs: bipartite graphs, their complements, their line graphs, the complements of their line graphs. Interestingly, this was all proved directly by Kőnig [61,60], long before the definition of perfect graphs.
We now turn our attention to a less classical class that is first presented in the proof of the SPGT: double split graphs. As it is presented in [20], the class is not closed under taking induced subgraphs, which is sometimes not convenient. So we prefer here to define directly doubled graphs, that are easily seen to form the class of induced subgraphs of double split graphs (as defined in [20]).
A good partition of a graph G is a partition (X, Y ) of V (G) (possibly, X = ∅ or Y = ∅) such that: • Every component of G[X] has at most two vertices, and every anticomponent of G[Y ] has at most two vertices.
, and every vertex v in C X ∪ C Y , there exists at most one edge and at most one antiedge between C X and C Y that is incident to v.
A graph is doubled if it has a good partition (for the sake of completeness, let us mention that a double split graph is a doubled graph such that G[X] (resp. G[Y ]) has at least two components (resp. anticomponents) and all components (resp. anticomponents) of G[X] (resp. G[Y ]) have two vertices). Doubled graphs are easily seen to be perfect by a direct colouring argument. They are closed under taking induced subgraphs and complements. A graph is basic if it belongs to at least one of the five classes defined here: bipartite, complement of bipartite, line graph of bipartite, complement of line graph of bipartite, and doubled graphs.
For each basic class, the characterization by excluding induced subgraphs is known (see Beineke [4] for line graphs and Alexeev, Fradkin and Kim [3] for doubled graphs); the recognition can be performed in polynomial time (see Lehot [62] or Roussopoulos [88] for line graphs and Maffray [72] for doubled graphs). Also the colouring and maximum clique problems can be solved in polynomial time (see Schrijver [90] for the 'historical classes' and Maffray [72] for doubled graphs). Note that the paper of Maffray [72] answers a question asked in a previous version of the present survey.

Further reading
In this section, we focused on the basic graphs that play an important role in the proof of the SPGT. But any class of graphs whose perfection is simple to prove can potentially serve as a basic class of a decomposition theorem, so all classes are potentially of interest. The book of Brandstädt, Le and Spinrad [11] is on general graph classes, but contains a lot of material on perfect graphs. The most complete catalog of classes of perfect graphs seems to be written by Hougardy [58], that describes 120 classes. Also Chapter 66 in Schrijver [90] contains a very complete survey about classes of perfect graphs. The book by Golumbic [51] surveys algorithmic aspects of several classes of perfect graphs.
Perhaps the most important class that we omit to present here is the seminal class of hole-free graphs, known as chordal graphs and introduced by Dirac [42] and Gallai [48]. It is the first class with a decomposition theorem, has some connections with the graph minors theory and tree-width, and is also important in fast graph searching algorithms. About that, a good starting point is Sections 9.7-9.8 in the book of Bondy and Murty [10]. Another important class, that has connections with ordered sets, is the class of comparability graphs introduced by Gallai [49] (the English translation by Maffray and Preissmann [73] contains a short survey).

Decompositions
By decomposition of a graph we mean a way to partition its vertices with some prescribed adjacencies. A decomposition is useful if it can be proved that a minimum counter-example to the SPGT cannot admit the decomposition. Indeed, suppose that we can prove a statement such as: 'every Berge graph is either basic or has a useful decomposition'. The SPGT can then be proved as follows: consider a minimum counter-example, i.e. a Berge graph, imperfect, and of minimum size. It does not admit the decomposition (because the decomposition is useful), and since it is imperfect, it cannot be basic, a contradiction to the statement.
The simplest useful decomposition, first observed in this context by Gallai [48], is the clique cutset, that is a clique whose removal yields a disconnected graph. It is easily seen to be useful, because gluing two perfect graphs along a clique yields a perfect graph.
In a graph G, substituting a graph H for a vertex v, means deleting v, adding a copy of H, making every neighbor of v complete to H, and every non-neighbor of v anticomplete to H. Along the lines of the proof of Lemma 2.2, it is easy to prove that substituting a perfect graph for a vertex of a perfect graph yields a perfect graph (this is therefore a variant of Lovász's replication lemma). It follows easily that a minimally imperfect graph does not admit a homogeneous set, where a homogeneous set of a graph G is a set H ⊆ V (G) such that 1 < |H| < |V (G)| and every vertex of G \ H is either complete or anticomplete to H.
A 1-join of a graph G, first defined by Cunningham [38], is a partition (X, Y ) of V (G) such that |X| ≥ 2, |Y | ≥ 2, and there exist A ⊆ X and B ⊆ Y such that A is complete to B and no other edges exist from X to Y . Again, 1-joins can be proved to be useful (this is proved by Cunningham [38], Bixby [9] and it also follows from Lemma 4.1 below).
Note that clique cutsets, homogeneous sets and 1-joins do not appear explicitly in Theorem 6.1. This is because they are not formally necessary, since their presence implies that the graph is basic or has another decomposition (namely the balanced skew partition, to be defined soon). We mention them because they are somehow present 'implicitly'; this sometimes shows up naturally in attempts to use Theorem 6.1 for algorithmic purpose. We now turn our attention to the decompositions that are actually used in Theorem 6.1. For each definition, we use the definition from [20], that sometimes differ slightly from the definition given in the paper where the decomposition is first presented (and where the proof of the usefulness of the decomposition is given).
A 2-join of a graph G, first defined by Cornuéjols and Cunningham [37], is a partition (X 1 , X 2 ) of V (G) such that there exist disjoint non-empty sets A 1 , B 1 ⊆ X 1 , A 2 , B 2 ⊆ X 2 satisfying: • A 1 is complete to A 2 , B 1 is complete to B 2 and these edges are the only ones between X 1 and X 2 ; • |X i | ≥ 3, i = 1, 2; • every component of G[X i ] intersects A i and B i , i = 1, 2; and is not a path of length two joining the members of A i and B i , i = 1, 2.
Cornuéjols and Cunningham [37] proved that a minimally imperfect graph admiting a 2-join must be an odd hole (so, 2-joins are useful). A reader who pays attention to technicalities may notice that here, path 2-joins are allowed (these are 2-joins such that for some i ∈ {1, 2}, |A i | = |B i | = 1 and G[X i ] is a path from the unique vertex in A i to the unique vertex in B i ). Some papers (mostly, these cosigned by Conforti, Cornuéjols or Vušković) restrict the notion of 2-joins to non-path 2-joins. In Section 10, the relevance of excluding path 2-joins is discussed. When X i , A i and B i are as above, it is customary to set C i = X i \ (A i ∪ B i ). It is easy to prove that in Berge graphs, all paths from A i to B i with interior in C i have the same parity (otherwise, an odd hole exists). Therefore, there are two kinds of 2-joins, according to this parity: odd and even 2-joins. If (X 1 , X 2 ) is a 2-join of G, then it is a complement 2-join of G.
When G is a graph and A ⊆ V (G), we denote by C(A) the sets of vertices of G complete to A and by C(A) the set of vertices of G anticomplete to A. A homogeneous pair (first defined in a slightly different way by Chvátal and Sbihi [31] who proved that they are useful) is a pair of disjoint sets A, B ⊆ V (G) such that |A|, |B| ≥ 2, every vertex of A has a neighbor and a non-neighbor in B, every vertex of B has a neighbor and a non-neighbor in All the decompositions presented so far are nice in the following sense. When applied recursively, they yield decomposition trees of polynomial size that allow solving several problems. The machinery is too heavy to be presented here, see Section 12. We now turn our attention to other kinds of cutset that do not have this nice property.
A star cutset (first defined by Chvátal [30]) in a graph G is a set S of vertices such that G \ S is disconnected and S contains a vertex v, called the center, complete to S \ v. The following is known as the star cutset lemma [30]. It remarkably generalizes the usefulness of clique cutsets, 1joins and homogeneous sets (because these decompositions all imply the presence of a star cutset). Proof. Let G be a minimally imperfect graph and suppose for a contradiction that G has a star cutset S centered at v. Let (X, Y ) be a partition of V (G\S) such that |X|, |Y | ≥ 1 and X is anticomplete to Y . We now prove that G satisfies the condition (iii) from Lemma 2.1 (this implies that G is perfect, giving the contradiction). Since every proper induced subgraph of G is perfect, it just remains to find the desired stable set in G. By condition (ii) from Lemma 2.1, there exists a stable set A X in G[S ∪ X] that contains v and intersects all maximum cliques of It is quite easy to turn the proof above into a colouring algorithm (that would for instance colour any perfect graph every induced subgraph of which is either basic or decomposable by a star cutset). The algorithm would output a stable set that intersects all maximum cliques, and along the lines of the proof of Lemma 2.1, this gives a colouring algorithm. Unfortunately, this algorithm does not run in polynomial time, because the star cutset can be very big, for instance be the entire graph except two vertices. In this case, the complexity analysis of the recursive calls leads to an exponential number of calls. There is a similar problem with the generalizations that we consider now. This is the main reason why the decomposition of Berge graphs does not lead to a polynomial time colouring algorithm.
A skew partition (first defined by Chvátal [30]) of a graph G is a partition is not anticonnected. In this case, we say that B is a skew cutset. Following a prophetic insight that some self-complementary decomposition generalizing the star cutset should play some role, Chvátal conjectured that a minimally imperfect graph has no skew partition, and a less formal statement, that skew partitions should appear in the decomposition of Berge graphs. Observe that if a graph on at least 5 vertices with at least one edge has a star cutset, then it has a skew partition. The proof of Chvatal's conjectures escaped the researchers, but several fruitful attempts were made. In particular, many special kinds of skew partitions were proved not to be in minimal imperfect graphs (see Reed [85] for a survey). In the opposite direction, a generalization of skew partitions was proved to decompose all Berge graphs in the following theorem [34]. A double star cutset in a graph G is a set S ⊆ V (G) such that G \ S is disconnected and S contains an edge uv such that every vertex of S is adjacent to at least one of u, v. Note that for a Berge graph G, the following gives in fact two pieces of information: one for G, one for G.

Theorem 4.2 (Conforti, Cornuéjols and Vušković 2004)
A graph with no odd hole is either basic, or has a 2-join or a double star cutset.
One of the breakthroughs made in the proof of the SPGT is the concept of balanced skew partition. For a graph G, a partition (skew or not) (A, B) of V (G) is balanced if every path of length at least 3, with ends in B and interior in A, and every antipath of length at least 3, with ends in A and interior in B has even length. It is straightforward to check that a partition (A, B) of a Berge graph is balanced if and only if adding a vertex complete to B and anticomplete to A yields a Berge graph.
As we will see, the notion of balanced skew partition is sufficiently particular to allow a short proof that a minimum counter-examples to the SPGT cannot contain it, and sufficiently general to be found in all non-basic Berge graphs that cannot be decomposed otherwise. Interestingly, Zambelli [99] notices that if a Berge graph on at least five vertices and with at least one edge has a star cutstet, then it has a balanced skew partition.  Proof. Let G be minimum imperfect Berge graph. Hence, χ(G) > ω(G). Note that by Theorem 2.3, G is also a minimum imperfect Berge graph. Let (A, B) be a balanced skew partition in G. So, A partitions into two sets A 1 and A 2 anticomplete to one another, and B partitions into two sets X and Y complete to one another. By Lemma 4.1, |A 1 |, |A 2 | ≥ 2, for otherwise, the unique vertex in A 1 or A 2 would be the center of a star cutset in G. From the minimality of G, it follows that every Berge graph ))-colouring. It follows that G has an ω(G)-colouring, a contradiction.
The following is maybe hopeless, because a proof would imply a direct argument for the skew partition conjecture (no such argument exists today). Also a proof of the following together with Theorem 4.2 would yield a new proof the SPGT. Observe that antiholes of length at least 6 have double star cutsets.
Question 4.5 Find a direct proof of the following: if G is a minimum Berge imperfect graph, then at least one of G, G admits no double star cutset.

Further reading
Rusu [89] wrote a survey about cutsets in perfect graphs, see also [87]. Reed [85] wrote a survey about skew partitions (on which this section is mostly based). It shows that many ideas of the proof presented above for balanced skew partitions are implicitly contained in several papers, namely in Hoàng [56], Olariu [78] and Roussel and Rubio [86].
An important question about decompositions is their detection in polynomial time.  [59]). Trotignon [94] showed that balanced skew partition are NP-hard to detect, but devised an O(n 9 )-time non-constructive algorithm that certifies whether an input Berge graph has or not a balanced skew partition.

Truemper configurations
Before going further, we need to define several special kinds of graphs, known as Truemper configurations. They appear in many contexts (sometimes in older papers, such as [98]).
A prism is a graph made of three vertex-disjoint paths P 1 = a 1 . . . b 1 , P 2 = a 2 . . . b 2 , P 3 = a 3 . . . b 3 of length at least 1, such that a 1 a 2 a 3 and b 1 b 2 b 3 are triangles and no edges exist between the paths except these of the two triangles. Observe that a prism in a Berge graph must have the lengths of the three paths of the same parity. The prism is odd or even according to this parity.
A pyramid is a graph made of three paths P 1 = a . . . b 1 , P 2 = a . . . b 2 , P 3 = a . . . b 3 of length at least 1, two of which have length at least 2, vertexdisjoint except at a, and such that b 1 b 2 b 3 is a triangle and no edges exist Figure 3: Pyramid, prism, theta and wheel (dashed lines represent paths) between the paths except these of the triangle and the three edges incident to a.
A theta is a graph made of three internally vertex-disjoint paths P 1 = a . . . b, P 2 = a . . . b, P 3 = a . . . b of length at least 2 and such that no edges exist between the paths except the three edges incident to a and the three edges incident to b.
Observe that the lengths of the paths in the three definitions are designed so that the union of any two of the paths form a hole.
A wheel is a graph formed by a hole H together with a vertex that have at least three neighbors in the hole.
A Truemper configuration is a graph isomorphic to a prism, a pyramid, a theta or a wheel. As we will see, Truemper configurations play a special role in the proof of the SPGT. First, a Berge graph has no pyramid (because among the three paths of a pyramid, two have the same parity, and their union forms an odd hole). This little fact is used very often to provide a contradiction when working with Berge graphs. As we will soon see, a long part of the proof is devoted to study the structure of a Berge graph that contains a prism, and another long part is devoted to a Berge graph that contains a wheel. And at the very end of the proof, it is proved that graphs not previously decomposed are bipartite, just as Berge thetas are. Note also that prisms can be defined as line graphs of thetas. This use of Truemper configurations is seemingly something deep and general as suggested by Vušković in a very complete survey [97] about Truemper configurations and how they are used (sometimes implicitly) in many decomposition theorems.
So far, no systematic study of the exclusion of Truemper configurations has been made. The most interesting question is perhaps the following.
Question 5.1 Are all wheel-free graphs χ-bounded by the same function?
Testing whether a graph contains or not some type of Truemper configuration is a question of interest. Detecting a theta in some input graph can be done in time O(n 11 ) (see Chudnovsky and Seymour [27]) and a pyramid in time O(n 9 ) (Chudnovsky, Cornuéjols, Liu, Seymour and Vušković [17]). Detecting a prism is NP-complete (Maffray and Trotignon [74]). Detecting a wheel is NP-complete, even when restricted to bipartite (and therefore perfect) graphs (Diot, Tavenas and Trotignon [41]). Detecting a prism or a pyramid can be done in time O(n 5 ) (Maffray and Trotignon [74]); so detecting a prism in a Berge graph is polynomial, since Berge graphs contain no pyramids. Detecting a theta or a pyramid can be done in time O(n 7 ) (Maffray, Trotignon and Vušković [76]). Detecting a prism or a theta can be done in time O(n 35 ) (Chudnovsky and Kapadia [18]). For similar questions, see Lévêque, Lin, Maffray and Trotignon [64]. 6 The strategy of the proof The main result in [20] is Theorem 6.1 below, and as we know from the previous sections, it implies the SPGT. Its statement is the result of a long sequence of attempts by many researchers, as explained in the introduction of [20] or in [87]. A slight variant on what seems now to be the right statement was first conjectured by Conforti, Cornuéjols and Vušković [33]. They proved it in the square-free case, and some of the arguments that they discovered are essential in the strategy described below (in particular, the attachments to prisms, and the use of Truemper configurations). The strategy used by Chudnovsky, Robertson, Seymour and Thomas to prove Theorem 6.1 is classical in structural graph theory. It consists in identifying a 'dense' basic class, and a 'sparse' basic class as we explain now. The 'dense' basic class does not contain the obstruction (here an odd hole or antihole) of course, but 'almost' contains it, so that if a graph G contains an induced dense subgraph H, then any vertex exterior to H must attach in a very specific way to H, either enlarging the basic graph to a bigger basic graph, or entailing a decomposition. Therefore, for the sake of proving the decomposition theorem, it can be assumed that this particular class of basic graphs is excluded. Then the process can be iterated with a new kind of dense basic graphs. The sparse class is what remains when all dense substructures are excluded. Observe that this method is in some sense wiser than proofs by induction. Finding the right induction hypothesis is time consuming because for every failure, one has to restart from scratch, while a lemma stating that some dense substructure entails a decomposition is just a true statement, that can be used forever, even if the strategy of the proof changes.
For proving Theorem 6.1 the sparse class is formed by bipartite graphs and their complements. The dense class is more complicated. At the beginning of the proof, it is formed by 'sufficiently' connected line graphs, their complements and doubled graphs. The simplest line graphs in this context are the odd and even prisms (that are the line graphs of bipartite thetas). To understand why prisms and their generalizations are 'dense', the reader can check as an exercice that a Berge graph formed of a prism and one vertex not in the prism is either a bigger line graph, or has a 2-join, or some kind of skew partition, namely a star cutset. For this purpose, it is very convenient to know that Berge graphs have no pyramids, and what makes this work is that prisms are 'close to' containing pyramids. Typical cases that should pop out from a proof attempt are represented in Fig. 4. Then the reader might try to prove a similar statement for the line graph of the 2-subdivision of K 4 , or to prove similar statements with the vertex outside of the prism replaced by some path with neighbors in exactly two paths of the structure for instance. All this should lead to variants on 10.1 from [20], whose proof is easy to read since it does not rely on any technical lemmas. More about attachments to prisms is explained in Section 8 below.
A sequence of about a dozen dense basic graphs is considered: first, several kinds of line graphs of bipartite subdivisions of K 4 , then even prisms, then long prisms (long means that at least one of the paths has length at least 2), then the double diamond (see Fig 5), then various kinds of wheels (that are not basic, but that contain skew partitions), and finally antiholes of length at least 6. For each of these dense basic classes, it is proved that containing it leads to being basic or having some decomposition, and therefore, the Berge graphs handled next may be assumed not to contain this kind of induced subgraph. At the end of this process, so many induced  subgraphs are excluded that the graph under consideration, or its complement, is bipartite. Needless to say, identifying this long sequence of 'dense' graphs is tour de force, especially since for each of them, the technicalities are really involved. In particular, the self-complementary graphs L(K 3,3 ) and L(K 3,3 \ e) (see Fig. 5) are a problem since they are basic in many ways (they are both line graph and complement of line graphs, and the later is also a doubled graph). Therefore, there are several ways to describe their structure, depending on the basic class, and the relevant one is known only from the rest of the graph. Despite all the deep technicalities, the objects considered in the proof of Theorem 6.1 are very combinatorial. This leads to the following question. Question 6.2 Can the proof of Theorem 6.1 be transformed into a polynomial time algorithm whose input is any graph G and whose output is either an odd hole, an odd antihole, or a partition of the vertices of G certifying one of the outcomes of Theorem 6.1?

Further reading
In [20], the global strategy of the proof is well explained at the beginning. More about the strategy is to be found in [92] and [19]. How structural methods can be used generally for classes closed under taking induced subgraphs is discussed in Chudnovsky and Seymour [23] and in Vušković [97]. To make a start on Question 6.2, the first step is the detection in polynomial time of the structures that are used in the proof (line graphs of a bipartite subdivision of K 4 , even prism and odd prism). Apart from wheels (that are NP-complete to detect as mentioned at the end of Section 5), they all can be detected in polynomial time in Berge graph, see Maffray and Trotignon [74].

The Roussel-Rubio lemma
We are now ready to invistigate some technicalities of the proof of the SPGT. A lemma due to Roussel and Rubio [86] is used at many steps in [20]. In fact, the authors of [20] rediscovered it (in joint work with Thomassen) and initially named it the wonderful lemma because of its many applications.
The Roussel-Rubio lemma states that, in a sense, any anticonnected set of vertices of a Berge graph behaves like a single vertex. How does a vertex v 'behave' in a Berge graph? If a path of odd length (at least 3) has both ends adjacent to v, then v must have other neighbors in the path, for otherwise there is an odd hole. The lemma states roughly that an anticonnected set T of vertices behaves similarly: if a path of odd length (at least 3) has both ends complete to T , then at least one internal vertex of the path is also complete to T . In fact, there are two situations where this statement fails (outcomes (iii) and (iv) below), and for the sake of induction, it is convenient to give similar properties for a path of even length. All this results in a more complicated statement. A T -edge is an edge whose ends are T -complete. When P = xx . . . y y is a path of length at least 3, a leap for P is a pair of non-adjacent vertices u, v such that N (u) ∩ V (P ) = {x, x , y} and N (v) ∩ V (P ) = {x, y , y}. Observe that if u, v is a leap for P , then V (P ) ∪ {u, v} induces a prism. We denote by P * the interior of a path P . If P is a path, vertex-disjoint from T and whose ends are T -complete, then one the following holds.
(i) P has even length and has an even number of T -edges; (ii) P has odd length and has an odd number of T -edges; (iii) P has odd length at least 3 and there is a leap for P in T ; (iv) P has length 3 and its two internal vertices are the endvertices of an antipath of odd length whose interior is in T .
Proof. We prove the lemma by induction on |V (P ) ∪ T |. If P has length at most 2, then we have outcome (i) or (ii). So let us assume that P has length at least 3. Put P = xx · · · y y. Let us suppose that outcomes (iii) does not hold for P . We distinguish between three cases. Case 1: There is a T -complete vertex in P * . Let z be such a vertex. By induction, we can apply the lemma to the path xP z and T . If xP z has odd length and there is a leap {u, v} for xP z in T , then (xP z) * ∪ {u, v, y} induces an odd hole. If xP z has length 3 and its two internal vertices are the endvertices of an odd antipath Q whose interior is in T , then Q ∪ {y} induces an odd antihole. So it must be that the number of T -edges in xP z and the length of xP z have the same parity. The same holds for zP y. So the number of T -edges in P and the length of P have the same parity, and we have outcome (i) or (ii). Case 2: T induces a stable set. We denote by ε the parity of the length of P . Mark the vertices of P that have at least one neighbor in T . Call an interval any subpath of P , of length at least 1, whose ends are marked and whose internal vertices are not. Since x and y are marked, the edges of P are partitioned by the intervals of P . We claim that every interval of P either has even length or has length 1. Indeed, suppose there is an interval of odd length, at least 3, say P = x . . . y , named so that x, x , y , y appear in this order along P . Let u and v be neighbors of x and y in T , respectively. If x and y have a common neighbor t in T then P ∪ {t} induces an odd hole. Hence u = v, x = x, y = y, v is not adjacent to x , and u is not adjacent to y . If x = x , then P ∪ {u, x, v} induces an odd hole. So, x = x and similarly, y = y . Hence, {u, v} is a leap, a contradiction. This proves our claim.
Hence, the number of intervals of length 1 in P has parity ε. Moreover, we claim that for every interval of length 1, there is a vertex in T adjacent to both its ends. Indeed, suppose that there is an interval x y such that x and y do not have a common neighbor in T . Let u be a neighbor of x in T , and let v be a neighbor of y with u = v, uy ∈ E(G), and vx ∈ E(G).
Note that x = x and y = y . If x = x , then {u, x, v, x , y } induces an odd hole. So, x = x and similarly y = y . Now {u, v} is a leap, a contradiction.
For every v ∈ T , denote by f (v) the set of all {v}-complete edges of P . Let v 1 , . . . , v n be the elements of T . We know that |f (v 1 ) ∪ · · · ∪ f (v n )| has parity ε, since, from the previous paragraph, it is equal to the number of the intervals of length 1. Moreover, by the sieve formula we have: By the induction hypothesis, we know that if S T , then the number of S-complete edges in P has parity ε. Hence if I {1, . . . , n}, then |∩ i∈I f (v i )| has parity ε. Thus, we can rewrite the above equality modulo 2 as: has parity ε, meaning that the number of T -edges in P has parity ε. It follows that one of (i) of (ii) holds. Case 3: We are neither in Case 1 nor in Case 2 (so T is not a stable set and there is no T -complete vertex in P * ). Let Q = u · · · v be a longest path of G[T ]. So Q has length at least 2 (since T is not a stable set), and T \ {u} and T \ {v} are anticonnected sets. By the induction hypothesis, we know that P has an odd number of T \ {u}-edges and an odd number of T \ {v}edges. Note that a T \ {u}-edge and a T \ {v}-edge have no common vertex, for otherwise there would be a T -complete vertex in P * . In particular all T \ {u}-edges and T \ {v}-edges are different.
Suppose that Q has even length. Let x u x u be a T \{u}-edge of P and y v y v be a T \{v}-edge of P such that, without loss of generality, x, x u , x u , y v , y v , y appear in this order on P . If x u is non-adjacent to y v then {x u , y v } ∪ Q induces an odd antihole. If x = x u then {x u , y v }∪Q induces an odd antihole. If y v = y then {x u , y v } ∪ Q induces an odd antihole. It follows that P = x u x u y v y v , but then P ∪ Q induces an odd antihole. Thus Q has odd length (at least 3).
Suppose that T \{u, v} is not anticonnected. Since T \{u} and T \{v} are anticonnected, there exists a vertex w in an anticomponent of G[T \ {u, v}] that does not contain Q * and such that w is adjacent in G to at least one of u, v; but then Q ∪ {w} induces in G[T ] either a chordless path longer than Q or an odd hole, a contradiction. So T \ {u, v} is anticonnected. Now we know that there is an odd number of T \ {u, v}-edges in P (by the induction hypothesis). Recall that P has an odd number of T \ {u}edges, an odd number of T \ {v}-edges, and that these are different, so these account for an even number of T \ {u, v}-edges; thus P has at least one T \ {u, v}-edge x y that is neither a T \ {u}-edge nor a T \ {v}-edge. We may assume that x, x , y , y appear in this order along P and that y ∈ P * . So y is non-adjacent to one of u, v, say v. Then y is adjacent to u, for otherwise Q ∪ {y } would induce an odd antihole. Then x is non-adjacent to u, for otherwise x y would be a T \ {v}-edge. Then x is adjacent to v, for otherwise Q ∪ {x } would induce an odd antihole. Then x = x for otherwise Q ∪ {x , y , x} would induce an odd antihole, and similarly y = y . So P = xx y y and Q ∪ {x , y } is a chordless odd path of G, and we have outcome (iv).
It is not easy to see how useful Lemma 7.1 is, so let us give now a simple application, that is 3.1 from [20]. Proof. It is easy to check that P 4 is the only graph H on at least four vertices such that both H and H are subgraphs of some path. It follows that if |V (C) ∩ V (D)| ≥ 4, then V (C) ∩ V (D) induces a P 4 , say abcd. So, there is a path P from a to d in G, such that abcdP a is the hole C; and there is an antipath Q from b to c such that bQcadb is the antihole D. Note that P and Q are both of odd length, at least 5.
The ends of P are Q * -complete. If P * contains a Q * -complete vertex v, then {v} ∪ V (Q) induces an odd antihole. Therefore, by Lemma 7.1 Q * contains a leap {u, v} for P , so some path P from u to v has the same interior as P . Observe that u and v are consecutive along Q, and because of the length of Q, one of b, c (say b) is complete to {u, v}. It follows that V (P ) ∪ {b} induces an odd hole.
We now give a corrolary of 7.1 that is used constantly in [20] (where it is called 2.2).

Corollary 7.3 Let T be an anticonnected set of vertices in a Berge graph
G. If P is a path with odd length at least 3, vertex-disjoint from T , whose ends are T -complete and such that no internal vertex of P is T -complete, then every T -complete vertex has a neighbor in P * .
Proof. Let v be a T -complete vertex, and suppose that v has no neighbor in P * (so v is not in V (P ) ∪ T ). Apply Lemma 7.1 to T and P . If outcome (iii) of Lemma 7.1 holds, then a path of odd length with same interior as P joins the members of the leap. Together with v, it forms an odd hole, a contradiction. If outcome (iv) of Lemma 7.1 holds, then the antipath of odd length can be completed to an odd antihole through v, a contradiction.

Further reading
Another proof of the Roussel-Rubio lemma is given in Maffray and Trotignon [75], where some applications are also presented. The proof given here in the case when T is a stable set is due to Kapoor, Vušković and Zambelli, see [95] where several very simple applications are presented.

Book from the Proof
The goal of this section is to present a self-contained lemma of [20] in order to give some taste of the technicalities. Let us replace this lemma in its context by stating informally how line graphs are handled.
A line graph K of a bipartite graph is formed of a bunch of cliques, and a bunch of paths linking them. If K is contained in a Berge graph G, a vertex v ∈ V (G \ K) is major if it has many (here at least 2) neighbors in each of the cliques, and minor if it has neighbors in at most one of the paths, or in at most one of the cliques. An important result is that every vertex is major or minor, or allows one to obtain a larger line graph. This is not fully true (Fig. 4 contains counter-examples), but vertices that are neither major nor minor can be considered as part of some of the paths in what is called a generalized line graph. Therefore, when the generalized line graphs are properly defined, it is true that every vertex is major or minor w.r.t. a maximal generalized line graph. A next step is to prove that connected (sometimes anticonnected) components of vertices of G\K behave in fact as a vertex. A reader wanting to know more details for components can read the proof of 10.1 in [20] and we deal with anticomponents below.
If there are no major vertices, the graph is formed of the line graph, and possibly a bunch of minor components. If some of these components attach to a clique, then there is a balanced skew partition, and if some attach to a path, there is a 2-join. If there are major vertices, then it can be proved that an anticomponent of these is formed of vertices that all major in the same way, meaning that they all attach to exactly the same vertices of the cliques. Therefore, an anticomponent of major vertices is complete to its attachment, and forms a skew cutset separating parts of the line graph. The next lemma (it is a variant of 7.3 from [20]) proves a statement of this form. It illustrates another breakthrough made in [20]: how the Roussel-Rubio lemma can be used to find skew partitions. Lemma 8.1 In a Berge graph G, let K be a prism with triangles a 1 a 2 a 3 and b 1 b 2 b 3 and paths P i = a i . . . b i , i = 1, 2, 3. Suppose that for i = 1, 2, 3, P i has length at least 2. Let Y be an anticonnected set of vertices such that each of them have at least two neighbors in {a 1 , a 2 , a 3 } and at least two neighbors in {b 1 , b 2 , b 3 } (so Y is disjoint from K). Then at least two members of {a 1 , a 2 , a 3 } and at least two members of {b 1 , b 2 Proof. Suppose not; then there is an antipath with interior in Y joining two vertices both in {a 1 , a 2 , a 3 } or both in {b 1 , b 2 , b 3 }. Let Q be a shortest such antipath. Suppose up to symmetry that Q is from a 1 to a 2 . Every vertex in Y is adjacent to either a 1 or a 2 , so Q has length at least 3. From the minimality of Q, a 3 is Q * -complete, and so is at least one of {b 1 , b 2 , b 3 }, say b i . Since Q can be completed to an antihole via a 1 b i a 2 , it follows that Q has even length, therefore at least 4. We set Q = a 1 q 1 . . . q n a 2 . Let a i be the neighbor of a i in P i , i = 1, 2 and P = a 1 P 1 b 1 b 2 P 2 a 2 .
(1) At least one internal vertex of P is (Q * \ q 1 )-complete and at least one internal vertex of P is (Q * \ q n )-complete.
If one of b 1 or b 2 is Q * -complete, the claim is obviously true. Otherwise, none of b 1 , b 2 is Q * -complete so there exists a antipath from b 1 to b 2 whose interior in Q * , and from the minimality of Q this antipath has the same interior as Q. It follows that one of b 1 , b 2 is complete to Q * \ q 1 and the other one is complete to Q * \ q n . This proves (1).
(2) If an internal vertex of P is (Q * \ q 1 )-complete or (Q * \ q n )-complete, then it is Q * -complete. If a 1 is (Q * \ q 1 )-complete, then it is Q * -complete.
If an internal vertex v of P is (Q * \ q n )-complete, then it is Q * -complete for otherwise, vq n Qa 1 v is an odd antihole. If v is a 1 or is an internal vertex of P , and v is (Q * \q 1 )-complete, then v is Q * -complete, for otherwise, vq 1 Qa 2 v is an odd antihole. This proves (2).
If both a 1 , a 2 are Q * -complete, then Q can be completed to an odd antihole via a 1 a 2 a 1 a 2 , a contradiction. So, up to symmetry, we suppose from here on that a 1 is not Q * -complete. It follows by (2) that a 1 is not Q * \ q 1 complete. Call x the Q \ q 1 complete vertex of P closest to a 1 along P . By (1), x exists and is an internal vertex of P . By (2), x is in fact Q * -complete.
If a 1 a 1 P x has odd length, then by Corollary 7.3 applied to a 1 a 1 P x and Q * \ q 1 , there is a contradiction because a 3 is (Q * \ q 1 )-complete and has no neighbor in the interior a 1 P x. So a 1 P x has even length. It follows that xP a 2 a 2 has odd length. By Corollary 7.3 applied to xP a 2 a 2 and Q * \ q n , and because of a 3 , there must be an internal vertex v of xP a 2 a 2 that is (Q * \ q n )-complete. By (2), v is in fact Q * -complete. But then, a 3 a 1 a 1 P x is odd, its ends are Q * -complete, but none of its internal vertex is Q * -complete. This contradicts Corollary 7.3 because of v.
The lemma above shows how the Roussel-Rubio lemma 'generates' antiholes to provide contradictions. Maybe it can be used to invistigate the structure of several subclasses of Berge graphs, for instance the next one.

Further reading
About technicalities, the best reading is of course Chudnovsky, Robertson, Seymour and Thomas [20]. The paper is very well organized: the first four sections are devoted to technical lemmas that are used extensively in the sequel. But as a result of this wise organization, it is very hard to extract a meaningful part: it is difficult to feel how useful the technical lemmas are without knowing the sequel, and the sequel is difficult to understand without mastering the technicalities of the lemmas. A reader seeking the easiest parts from [20] should try 15.1, Section 15 or Section 16. Section 10 is devoted to the even prism and is a self-contained chunk that has fewer technicalities than the rest of the paper (but still relies a lot on technical lemmas of the previous sections).
A reader might want to read self-contained papers using the same kind of technicalities as [20] in simpler situations. For attachement to line graphs, a possible reading is Lévêque, Maffray and Trotignon [66] (where Question 5.1 is partially answered by the way). About how attachments to a wheel can be used to decompose a class, Radovanović and Vušković [82] is a good reading.

Recognizing perfect graphs
From here on, we investigate works on perfect graphs that were done after the proof of the SPGT. Soon after the proof of the SPGT, another open question was solved. Chudnovsky, Cornuéjols, Liu, Seymour and Vušković [17] found a polynomial time algorithm that decides whether an input graph is Berge. Observe that this algorithm is independent from the SPGT. It takes any graph G as an input and outputs in time O(n 9 ) an odd hole-orantihole of G (if any). We give here a brief outline (that is a copy from the introduction of [17]). In what follows, G is the input graph of the algorithm.
[. . . ] we would like to decide either that G is not Berge, or that G contains no odd hole. (To test Bergeness, we just run this algorithm on G and then again on the complement of G.) If there is an odd hole in G, then there is a shortest one, say C. A vertex of the remainder of G is C-major if its set of neighbours in C is not a subset of the vertex set of any 3-vertex path of C; and C is clean (in G) if there are no C-major vertices in G. If there happens to be a clean shortest odd hole in G, then it stands out and can be detected relatively easily; and that essentially is the first step of our algorithm, a routine to test whether there is a clean shortest odd hole. The remainder of the algorithm consists of reducing the general problem to the 'clean' case that was just handled. If C is a shortest odd hole in G, let us say a subset X of V (G) is a cleaner for C if X ∩ V (C) = ∅ and every C-major vertex belongs to X. Thus if X is a cleaner for C then C is a clean hole in G \ X. The idea of the remainder of the algorithm is to generate polynomially many subsets of V (G), such that if there is a shortest odd hole C in G, then one of the subsets will be a cleaner for C. If we can do that, then we delete each of these subsets in turn, thereby generating polynomially many induced subgraphs; and we know that there is an odd hole in G if and only if in one of these subgraphs there is a clean shortest odd hole. Thus we can decide whether G has an odd hole by testing whether any of these subgraphs has a clean shortest odd hole. Let us now explain briefly the two steps from the sketch above. The second step relies on a powerful technique discovered by Conforti and Rao [35], called cleaning, which consists in 'guessing' a cleaner. Here, the way to guess the cleaner comes from Roussel-Rubio like lemmas, saying that the set X of vertices vertices to be 'guessed', that are all major vertices of some possible smallest odd hole, are all common neighbors of some set S (of size bounded by constant) of neighbors. Therefore, one can enumerate all possible S's by brute-force, and for each of them nominate X as the set of S-complete vertices.
The first step relies on the shortest path detector, a method designed by Chudnovsky and Seymour [17] that is used twice in the algorithm: once to detect a clean odd hole, and once to detect a pyramid. Detecting a pyramid is needed in a preprocessing step that we omitted to explain in the sketch above. It consists in the detection of several substructures certifying that the graph is not Berge, and one of them is the pyramid (that contains an odd hole).
To explain the shortest path detector, we give here a simpler algorithm that detects prisms in graphs with no pyramids (recall that in general graphs, the problem is NP-complete). This algorithm is not published because a faster one exists, see [74]. A shortest path detector always relies on a lemma stating in the smallest substructure of the kind that we are looking for, a path linking two particular vertices of the substructure can be replaced by any shortest path.
Lemma 9.2 Let G be a graph with no pyramid. Let K be a smallest prism in G. Suppose that K is formed by paths P 1 , P 2 , P 3 , with triangles {a 1 , a 2 , a 3 } and {b 1 , b 2 , b 3 }, so that, for i = 1, 2, 3, path P i is from a i to b i . Then: If R i is any shortest path from a i to b i whose interior vertices are not adjacent to a i+1 , a i+2 , b i+1 or b i+2 , then R i , P i+1 , P i+2 form a prism on |V (K)| vertices in G, with triangles {a 1 , a 2 , a 3 } and {b 1 , b 2 , b 3 } (the addition of subscripts is taken modulo 3).
Proof. Suppose that the lemma fails for say i = 1. So, some interior vertex of R has neighbors in the interior of P 2 or P 3 . Let x be such a vertex, closest to a 1 along R. Let a 2 (resp. a 3 ) be the neighbor of a 2 (resp. a 3 ) along P 2 (resp. P 3 ). Let Q = a 2 P 2 b 2 b 3 P 3 a 3 . Let y (resp. z) be the neighbor of x closest to a 2 (resp. a 3 ) along Q.
If y = z then yxRa 1 , yQa 2 a 2 and yQa 3 a 3 form a pyramid, a contradiction. If y = z and yz / ∈ E(G) then xRa 1 , xyQa 2 a 2 and xzQa 3 a 3 form a pyramid, a contradiction. If yz ∈ E(G) then xRa 1 , yQa 2 a 2 and zQa 3 a 3 form a prism on less vertices than K, a contradiction. Now detecting a prism in a graph with no pyramid can be performed as follows. For all 6-tuples (a 1 , a 2 , a 3 , b 1 , b 2 form a prism, and if so output it. If no triple of paths forms a prism, output that the graph contains no prism. If the algorithm outputs a prism, this is obviously a correct answer: the graph contains a prism. Suppose conversely that the graph contains a prism. Then it contains a smallest prism with triangles {a 1 , a 2 , a 3 } and {b 1 , b 2 , b 3 }. At some step, the algorithm will check this 6-tuple (unless a prism is discovered before, but then the correctness is proved anyway). By three applications of Lemma 9.2, we see that the three paths R 1 , R 2 , R 3 form a prism that is output. All this take time O(n 8 ).
The following is still open.

Question 9.3
Is there a polynomial time algorithm to decide whether an input graph has an odd hole?

Further reading
In [17], another algorithm for recognizing Berge graphs is given. It relies on decompositions and uses Theorem 4.2. Detecting odd holes can be solved in polynomial time under the assumption that the largest size of a clique in the input graph is bounded by some constant. This is proved by Conforti, Cornuéjols, Liu, Vušković and Zambelli [32] that is a good reading for understanding the main ideas of the recognition of Berge graphs. A combination of cleaning and shortest path detector is used by Chudnovsky, Seymour and Trotignon [26] to decide in polynomial time whether a graph contains a subdivision of the net (the net is the graph obtained from a triangle by adding a pendant edge at each vertex).

Berge trigraphs
An obvious question about Theorem 6.1 is whether it is best possible. Is each outcome necessary? Are there outcomes that can be made more precise? A careful reader of [20] might notice that the outcome 'homogeneous pair' is obtained only once in the whole proof, and might therefore wonder whether it is really necessary. Chudnovsky proved it is not. Let us explain how. A way to proceed is to consider a smallest Berge graph G such that the homogeneous pair is the only outcome satisfied by G in Theorem 6.1, and to look for a contradiction. A natural idea is then to 'contract' a homogeneous pair (A, B) in order to find a smaller Berge graph G . Then, apply Theorem 6.1 to G , and prove that any outcome of Theorem 6.1 in G yields an outcome in G (because G and G are very similar). From the initial assumption, G therefore satisfies no outcome of Theorem 6.1, and this provides a contradiction. We call this method bootstrap, because it improves structural theorems somehow for free. The natural way to 'contract' a homogeneous pair (A, B) of G is to replace A (resp. B) by a vertex a (resp. b) complete to C(A) (resp. C(B)) and anticomplete to C(A) (resp. C(B)). The bootstrap method is hard to implement in this context. The problem is with ab: should it be an edge or an antiedge of G ? Both choices lead to difficult technicalities: if ab is chosen to be an antiedge, it could be that that some skew cutset separates a from b in G , while A and B are linked in G. If a is chosen to be adjacent to b, it could be that the same phenomenon happens in the complement. No neat example of these bad phenomena can be given, because as we will see, it is true that the outcome 'homogeneous pair' is not necessary in Theorem 6.1. But any attempt of proof will face this issue and is likely to fail.
The idea of Chudnovsky is to leave undecided the adjacency between a and b in G . To this purpose, she defines trigraphs as graphs with edges, antiedges, and a third kind of adjacency: switchable pair. For every pair of distinct vertices x and y, xy is an edge, an antiedge or a switchable pair. A realization G of a trigraph T is any graph on V (T ) such that all edges (resp. antiedges) of T are edges (resp. antiedges) of G (so, every switchable pair is transformed into an edge or an antiedge). A trigraph is Berge if every realization is Berge. We do not give the long list of definitions that translates naturally the vocabulary of graphs to trigraphs. The key point is in the definitions of the decompositions: all the 'important' edges in definitions of decompositions are not allowed to be switchable pairs. For instance, if (X, Y ) is a 2-join of a trigraph T , no switchable pair of T is from X to Y . If (X, Y ) is a skew partition of a trigraph T , it must be that X is partitioned into X 1 and X 2 such that no edge and no switchable pair exists between X 1 and X 2 , and it must be that Y is partitioned into Y 1 and Y 2 such that no antiedge and no switchable pair exists between Y 1 and Y 2 . It is easy to guess how useful this requirement is: for instance, when building G from G as in the paragraph above, ab is defined to be a switchable pair. So, the problem that we mentioned with the skew cutset separating a from b does not exists anymore.
Of course, the slight problem with this notion of trigraph is that the proof of Theorem 6.1 has to be done again from the beginning for Berge trigraphs. Chudnovsky proved several decomposition theorems similar to Theorem 6.1 for Berge trigraphs. The proof of the main one is self-contained and runs along more than 200 pages. We do not give the precise statements here, it would be pointless since we do not give the precise definitions of decompositions and basic classes of trigraph. The precise statements of the theorems are in [15], where only parts of the proofs are given. The complete proof is in [14]. With trigraphs, the bootstrap method works smoothly and yields the following (that we translate back to graphs, since a graph is a particular trigraph).
Theorem 10.1 (Chudnovsky 2003) Every Berge graph is basic, or has a 2-join, a complement 2-join or a balanced skew partition.
An interesting feature of trigraphs is that additional conditions can be added. For instance, a monogamous trigraph is a trigraph such that every vertex is member of at most one switchable pair. Monogamous trigraphs are very convenient to handle the interactions of odd 2-joins and homogenous pairs. When a monogamous trigraph T has a homogeneous pair (A, B), a smaller trigraph T can be constructed as follows: replace A (resp. B) by a vertex a (resp. b) strongly complete to C(A) (resp. C(B)) and strongly anticomplete to C(A) (resp. C(B)) (here strongly means that only real edges are used, not switchable pairs), and link a to b by a switchable pair. When a monogamous trigraph T has an odd 2-join (X 1 , X 2 ) with sets A 1 , B 1 , C 1 , A 2 , B 2 , C 2 as in the definition, a smaller trigraph T 2 can be constructed as follows: delete C 1 replace A 1 (resp. B 1 ) by a vertex a 1 (resp. b 1 ) strongly complete to A 2 (resp. B 2 ) and strongly anticomplete to B 2 ∪ C 2 (resp. A 2 ∪ C 2 ), and link a 1 to b 1 by a switchable pair. When applied iteratively, this way of constructing blocks of decompositions preserves the property of being monogamous, and shows that all the decompositions used in the process do not cross. A slightly more general notion of trigraph is defined in [28] to handle interactions between 2-joins, complement 2-joins and homogeneous pairs.
Another potential improvement of Theorem 6.1 is about the technical requirements in the definition of a 2-join. Some authors consider only nonpath 2-joins (already defined page 10). In some applications, it is essential to use non-path 2-joins, because one needs to replace one side of the 2-join by a long path to recurse (in proof by induction, or in algorithms), and this obviously fails if the side is already a long path. Trotignon [94] investigated this question and obtained the following result (with the bootstrap method for graphs starting from Theorem 10.1). Path cobipartite graphs and path double-split graphs are Berge graphs obtained by subdividing edges in complement of bipartite graphs and in double split graphs respectively (a more precise definition can be given, but this one is enough here). Observe that subdividing an edge in any graph creates a path 2-join.

Theorem 10.2 (Trotignon 2008)
If G is a Berge graph, then G is basic, or one of G, G is a path-cobipartite graph, or one of G, G is a path-double split graph, or one of G, G has a non-path 2-join, or G has a balanced skew partition, or one of G, G has a homogeneous pair and a path 2-join.
Observe that this theorem shows that homogeneous pairs are not necessary to decompose Berge graphs, that path 2-joins are not necessary to decompose Berge graphs, but does not show that one can get rid of both outcomes. We now give examples showing that every outcome of Theorem 10.2 is needed. In Fig. 6 and 7, a path cobipartite graph and a path double-split graph are represented. They both have a path 2-join, showing that to get rid of path 2-joins, the two new basic classes are really needed. The graph represented in Fig. 8 is interesting because it is decomposable only by a path 2-join or by a homogeneous pair, showing that it is impossible to get rid of both outcomes. Obtaining graphs uniquely decomposable by a 2-join (we mean that that they are not basic and that the 2-join is the only way to decompose them) is easy by the following recipe. Consider a Berge graph G i (i = 1, 2) that contains a path P i of length 3 from a i to b i and such that A i = N (a i ) and B i = N (b i ) are disjoint. Now take the disjoint union of G 1 and G 2 , and add all possible edges between A 1 and A 2 and between B 1 and B 2 . The resulting graph obviously has a 2-join, and if G 1 and G 2 are sufficiently general, this is the only decomposition. This recipe can be applied to the graphs from Fig. 6 and 7 for instance. On Fig. 10, a Berge graph uniquely decomposable by a balanced skew partition is represented.
Not much work has been devoted to the algorithmic aspects of trigraphs. The following is still open.

Further reading
It seems now that trigraphs are an important general tool in structural graph theory, as suggested by their use in the study of claw-free graphs (see Chudnovsky and Seymour [22]) and bull-free graphs (see Chudnovsky [16]). About algorithms for Berge trigraphs, Chudnovsky, Trotignon, Trunck and Vušković [28] seems to be the only available reference.

Even pairs: a shorter proof of the SPGT
An even pair in a graph is a pair {x, y} of vertices such that every path between them has even length. This notion is involved in algorithmic aspects of perfect graphs and allows to significantly shorten the proof of the SPGT. Meyniel [77] proved the following.
Theorem 11.1 (Meyniel 1987) A minimally imperfect graph has no even pair. Therefore, even pairs could be an ingredient of a useful decomposition theorem for Berge graphs. Given two vertices x, y in a graph G, the operation of contracting them means removing x and y and adding one vertex with edges to every vertex of G \ {x, y} that is adjacent in G to at least one of x, y; we denote by G/xy the graph that results from this operation. Fonlupt and Uhry [46] proved that if G is a perfect graph and {x, y} is an even pair in G, then the graph G/xy is perfect and has the same chromatic number as G. In particular, given a χ(G/xy)-colouring c of the vertices of G/xy, one can easily obtain a χ(G)-colouring of the vertices of G as follows: keep the colour for every vertex different from x, y; assign to x and y the colour assigned by c to the contracted vertex. This idea could be the basis for a conceptually simple colouring algorithm for Berge graphs: as long as the graph has an even pair, contract any such pair; when there is no even pair find a colouring c of the contracted graph and, applying the procedure above repeatedly, derive from c a colouring of the original graph. The algorithm for recognizing Berge graphs mentioned at the end of the preceding paragraph can be used to detect an even pair in a Berge graph G; indeed, it is easy to see that two non-adjacent vertices a, b form an even pair in G if and only if the graph obtained by adding a vertex adjacent only to a and b is Berge. Thus, given a Berge graph G, one can try to colour its vertices by keeping contracting even pairs until none can be found. Then some questions arise: what are the Berge graphs with no even pair? What are, on the contrary, the graphs for which a sequence of even-pair contractions leads to graphs that are trivially easy to colour?
Bertschi [8] proposed the following definitions. A graph G is even contractile if either G is a clique or there exists a sequence G 0 , . . . , G k of graphs such that G = G 0 , for i = 0, . . . , k − 1 the graph G i has an even pair {x i , y i } such that G i+1 = G i /x i y i , and G k is a clique. A graph G is perfectly contractile if every induced subgraph of G is even contractile.
A simple observation is that odd holes and antiholes of length at least 5 have no even pairs. Also some Berge graphs have no even pairs, such as C 6 , L(K 3,3 )\e, and more generally sufficiently connected line graphs of bipartite graphs (see Hougardy [57] for more about that), and every even antihole of length at least 6. In fact every known example of a Berge graph with no even pair either contains an odd prism or an antihole. Odd prisms different from C 6 have even pair, but they are not perfectly contractile (any attempt to contract them leads to C 6 ). This justifies the following definitions. Grenoble graphs are these graphs with no odd holes, no antihole of length at least 5 and no odd prism. Artemis graphs are these graphs with no odd holes, no antiholes of length at least 5 and no prisms. To prove the existence an even pair in an Artemis graph, an idea is to consider a shortest hole H, and two vertices u, v at distance 2 along H, with a common neighbor t ∈ V (H). As shown in Fig. 9, {a, b} may fail to be an even pair because of a which is the second vertex of a P 4 from a to b. However, one may complain that H is not the 'best' hole, the hole H obtained by replacing a by a is better, because {a , b} is an even pair of G. In this sense, a is 'better' than a. In the square-free case, Linhares and Maffray [67] showed that the neighborhood of t contains two cliques A and B. On A (and also on B), there exists an order (corresponding to the idea of a vertex better than another one). A maximal element in A and a maximal element in B forms an even pair of G. This method was extended by Maffray and Trotignon [75] to general Artemis graphs by using the Roussel-Rubio lemma.

Theorem 11.2 (Maffray and Trotignon 2005) Every Artemis graph is perfectly contractile.
This theorem can be transformed into a colouring algorithm [65] that generalizes several well known algorithms for colouring classes of perfect graphs, such as Meyniel graphs and weakly chordal graphs. It yields a combinatorial polynomial time colouring algorithm for perfectly orderable graphs (none was known before). The proof of the next theorem from [24] uses some technics of the proof of Theorem 11.3, is very readable, and as we will see saves about 50 pages in the proof of the SPGT. An odd wheel (C, T ) in a graph G consists of a hole C of length at least six, and a nonempty anticonnected subset T ⊆ V (G) \ V (C), such that at least three vertices of C are T -complete, and there is a path P of C with odd length at least 3, such that its ends are not T -complete and all its internal vertices are T -complete. A long prism is a prism such that at least one the paths has length at least 2. Let us say that G is impoverished if G is Berge, and G and G both contain no odd wheel, long prism or double diamond. A dominant pair in G is a pair (x, y) of nonadjacent vertices such that every other vertex of G is adjacent to at least one of x, y.
Theorem 11.4 (Chudnovsky and Seymour, 2009) If G is impoverished, then either G admits a star cutset or an even pair or a dominant pair, or G is a complete graph.
It is not very difficult to prove that a minimally imperfect graph has no dominant pair (see [24]), so it follows easily by Theorem 11.1 and Lemma 4.1 that every impoverished graph is perfect. Since the last 55 pages of the proof of the SPGT are devoted to finding a skew partition in an impoverished graph, they are no longer necessary and can be replaced by the 8 pages needed to prove Theorem 11.4.
A neat generalization of Theorem 11.3 is the following conjecture (see [44]).

Conjecture 11.5 (Everett and Reed) Every Grenoble graph is perfectly contractile.
To prove perfection for a class C, a statement of the following form is enough: every graph in C has an even pair, or its complement has an even pair. Note that this does not hold for all Berge graphs as shown by L(K 3,3 \ e) (see Fig. 5). It seems that the only known theorem of this form is the following from [39]. The bull is the graph obtained from the triangle by adding two pending edges at different vertices.
Theorem 11.6 (de Figueiredo, Maffray and Porto, 1997) If G is a bull-free Berge graph with at least two vertices then at least one of G or G has an even pair.
A graph G is bipartisan if it is Berge and contains no L(K 3,3 \ e), no double diamond, and none of G, G contains a long prism (a prism is long when at least one of three paths of the prism has length at least 2). Observe that every bull-free Berge graph is bipartisan. An intermediate result of [20] is that a bipartisan graph is bipartite, complement of bipartite, or has a balanced skew partition. A direct proof of the following conjecture (published in [12] and [24]) would generalize Theorem 11.6 and could shorten the proof of the SPGT.
Conjecture 11.7 (Maffray, 2002) If G is bipartisan with at least two vertices, then one of G, G contains an even pair.

Further reading
A good survey on even pairs is Everett, de Figueiredo, Linhares Sales, Maffray, Porto and Reed [44]. It seems that even pairs is a conjecturecornucopia: other conjectures on even pairs can be found in Burlet, Maffray and Trotignon [12] or in Lévêque and de Werra [63]. Very short proofs of the existence of even pairs in classical classes of perfect graphs (Meyniel graphs and weakly chordal graphs) can be found in Trotignon and Vušković [95].

Colouring perfect graphs
In the 1980s, Gröstchel, Lovász and Schrijver [52] devised a polynomial time algorithm that colours any input perfect graph. This algorithm relies on the ellipsoid method, and one may wonder whether a more combinatorial algorithm exists. Even if there is no formal definition of what a combinatorial algorithm should be, most mathematicians agree that an algorithm that relies on graphs searches and decompositions, and even on classical linear programming, can be called 'combinatorial' and that the ellipsoid method cannot. So this question is considered open. A more precise question is whether a fast colouring algorithm can be derived from Theorem 6.1. We investigate here recent progress in this direction.
We start with a combinatorial polynomial time colouring algorithm for perfect graphs, due to Grötschel, Lovász and Schrijver [52], under the assumption that a subroutine for computing a maximum weighted stable set is available. Here weights are not essential, because they can be simulated by replications, but we use them for convenience and because some subclasses of perfect graphs are not closed under replication. We suppose that C is a subclass of perfect graphs, and that there is an O(n k ) algorithm A that computes a maximum weighted stable set and a maximum weighted clique for any input graph in C (so C needs not be closed under taking complement). Observe that we do not assume that C is closed under replication or even under taking induced subgraphs. In what follows, n denotes the number of vertices of the graph under consideration.
Lemma 12.1 There is an algorithm with the following specification: Input: A graph G in C, and a sequence K 1 , . . . , K t of maximum cliques of G where t ≤ n.
Output: A stable set of G that intersects each K i , i = 1, . . . , t.
Running time: O(n k ) Proof. By ω(G) we mean here the maximum cardinality of a clique in G. Give to each vertex v the weight y v = |{i; v ∈ K i }|. Note that this weight is possibly zero. With Algorithm A, compute a maximum weighted stable set S of G. Let us consider the graph G obtained from G by replicating y v times each vertex v. So each vertex v in G becomes a stable set Y v of size y v in G and between two such stable sets Y u , Y v there are all possible edges if uv ∈ E(G) and no edges otherwise. Note that vertices of weight zero in G are not in V (G ). Note also that G may fail to be in C, but it is easily seen to be perfect. By replicating y v times each vertex v of S, we obtain a stable set S of G of maximum cardinality.
By construction, V (G ) can be partitioned into t cliques of size ω(G) that form an optimal colouring of G because ω(G ) = ω(G). Since by Theorem 2.3 G is perfect, |S | = t. So, in G, S intersects every K i , i ∈ {1, . . . , t}.
Theorem 12.2 (Gröstchel, Lovász and Schrijver 1988) There exists an algorithm of complexity O(n k+2 ) whose input is a graph from C and whose output is an optimal colouring of G.
Proof. As in the proof of Lemma 2.1, we only need to show how to find a stable set S intersecting all maximum cliques of G, since we can apply recursion to G \ S (by giving weight 0 to vertices of S). Start with t = 0. At each iteration, we have a list of t maximum cliques K 1 , . . . , K t and we compute by the algorithm in Lemma 12.1 a stable set S that intersects every K i , i ∈ {1, . . . , t}. If ω(G \ S) < ω(G) then S intersects every maximum clique, otherwise we can compute a maximum clique K t+1 of G\S (by giving weight 0 to vertices of S). This will eventually find the desired stable set, the only problem being the number of iterations. We show that this number is bounded by n.
Let M t be the incidence matrix of the cliques K 1 , . . . , K t . So the columns of M t correspond to the vertices of G and each row is a clique (we see K i as row vector). We prove by induction that the rows of M t are independent. So, we assume that the rows of M t are independent and prove that this holds again for M t+1 .
So the matrices M 1 , M 2 , . . . cannot have more than n rows. Hence, there are at most |V (G)| iterations.
By Theorem 12.2, we know that finding a maximum weighted stable set is enough to solve the colouring problem. Our question now is whether Theorem 6.1 (or one of its variants from Section 10) helps to find a maximum weighted stable set. It turns out that the question is easy for all basic classes (for the historical ones, see [90] and for doubled graphs, see [28]). Also homogeneous pairs and complement 2-joins are not very hard to handle (see [28]).
For 2-joins, the situation is more complicated because a maximum stable set may overlap a 2-join in many ways. To illustrate the problem, we start with an NP-hardness result. We define a class C of graphs for which computing a maximum stable set is NP-hard. The interesting feature of C is that all graphs in C are decomposable along 2-joins into one bipartite graph and several gem-wheels where a gem-wheel is any graph made of an induced cycle of length at least 5 together with a vertex adjacent to exactly four consecutive vertices of the cycle. Note that a gem-wheel is a line graph (of a cycle with one chord) and that computing a maximum weighted stable set in line graph G = L(R) means computing a maximum weighted matching in R, which can be done by Edmonds's algorithm [43]. Therefore, the NPcompleteness result below shows that being able to decompose along 2-joins into 'easy' graphs is not enough in general to compute stables sets.
A flat path in a graph is path whose internal vertices have degree 2 (in the graph). Extending a flat path P = p 1 . . . p k of a graph means deleting the interior vertices of P and adding three vertices x, y, z and the following edges: p 1 x, xy, yp k , zp 1 , zx, zy, zp k . By extending a graph G we mean extending all paths of M where M is a set of vertex-disjoint flat paths of length at least 3 of G. Class C is the class of all graphs obtained by extending 2-connected bipartite graphs. From the definition, it is clear that all graphs of C are decomposable along non-path 2-joins. One leaf of a decomposition tree will be the underlying bipartite graph. All the others leaves will be gem-wheels.
We call 4-subdivision any graph G obtained from a graph H by subdividing every edge four times. More precisely, every edge uv of H is replaced by an induced path uabcdv where a, b, c, d are of degree two. It is easy to see that α(G) = α(H) + 2|E(H)|. This construction, essentially due to Poljak [80], yields the next result observed by Naves (see [96]): Theorem 12.3 (Naves, Trotignon and Vušković 2012) The problem whose instance is a graph G from C and an integer k, and whose question is 'Does G contain a stable set of size at least k' is NP-complete.
Proof. Let H be any graph. First we subdivide 5 times every edge of H. So each edge ab is replaced by P 7 = ap 1 . . . p 5 b. The graph H obtained is bipartite. Now we build an extension G of H by replacing all the P 5 's p 1 . . . p 5 arising from the subdivisions in the previous step by P 4 's. And for each P 4 we add a new vertex complete to it and we call apex vertices all these new vertices. The graph G that we obtain is in C. It is easy to see that there exists a maximum stable set of G that contain no apex vertex because an apex vertex of a maximum stable set can be replaced by one vertex of its neighborhood. So, we call G the graph obtained from G by deleting all the apex vertices and see that α(G ) = α(G). Also, G is the 4-subdivision arising from H. So from the remark above, maximum stable sets in H and G have sizes that differ by 2|E(H)|.
We now explain how 2-joins can in fact help to find stable sets in Berge graphs. If (X, Y ) is a 2-join of a graph G then let X 1 = X, X 2 = Y and let A 1 , B 1 , C 1 , A 2 , B 2 , C 2 be as in the definition of a 2-join. We define α AC = α(G[A 1 ∪ C 1 ]), α BC = α(G[B 1 ∪ C 1 ]), α C = α(G[C 1 ]) and α X = α(G[X 1 ]). Let w be the weight function on V (G). When H is an induced subgraph of G, or a subset of V (G), w(H) denotes the sum of the weights of vertices in H. The following simple lemma describes the situation.
Lemma 12.4 Let S be a maximum weighted strong stable set of G. Then exactly one of the following holds: (i) S ∩ A 1 = ∅, S ∩ B 1 = ∅, S ∩ X 1 is a maximum weighted strong stable set of G[A 1 ∪ C 1 ] and w(S ∩ X 1 ) = α AC ; (ii) S ∩ A 1 = ∅, S ∩ B 1 = ∅, S ∩ X 1 is a maximum weighted strong stable set of G[B 1 ∪ C 1 ] and w(S ∩ X 1 ) = α BC ; (iii) S ∩ A 1 = ∅, S ∩ B 1 = ∅, S ∩ X 1 is a maximum weighted strong stable set of G[C 1 ] and w(S ∩ X 1 ) = α C ; (iv) S ∩ A 1 = ∅, S ∩ B 1 = ∅, S ∩ X 1 is a maximum weighted strong stable set of G[X 1 ] and w(S ∩ X 1 ) = α X .
Proof. Follows directly from the definition of a 2-join.
The next inequalities are from [96]. They say how stable sets and 2-joins overlap in Berge graphs.
Proof. Let D be a stable set of G[X 1 ] of weight α X and C a stable set of G[C 1 ] of weight α C . In the bipartite graph G[(C ∪ D], we denote by Y A (resp. Y B ) the set of those vertices of C ∪ D for which there exists a path in G[C ∪ D] joining them to some vertex of D ∩ A 1 (resp. D ∩ B 1 ). Note that from the definition, D ∩ A 1 ⊆ Y A , D ∩ B 1 ⊆ Y B and there are no edges between Y A ∪ Y B and (C ∪ D) \ (Y A ∪ Y B ). We claim that Y A ∩ Y B = ∅, and Y A is anticomplete to Y B . Suppose not. Then there exists a path P in G[C ∪ D] from a vertex of D ∩ A 1 to a vertex of D ∩ B 1 . We may assume that P is minimal with respect to this property, and so the interior of P is in C 1 ; consequently P is of even length because G[C ∪ D] is bipartite. This contradicts the assumption that (X 1 , X 2 ) is odd. Now we set: From all the definitions and properties above, Z A and Z B are stable sets and Z A ⊆ A 1 ∪ C 1 and Z B ⊆ B 1 ∪ C 1 . So, α C + α X = w(Z A ) + w(Z B ) ≤ α AC + α BC . Lemma 12.7 (Trotignon and Vušković 2012) If (X 1 , X 2 ) is an even 2join of G, then α AC + α BC ≤ α C + α X .
Proof. Let A be a stable set of G[A 1 ∪ C 1 ] of weight α AC and B a stable set of G[B 1 ∪ C 1 ] of weight α BC . In the bipartite graph G[A ∪ B], we denote by Y A (resp. Y B ) the set of those vertices of A ∪ B for which there exists a path P in G[A ∪ B] joining them to a vertex of A ∩ A 1 (resp. B ∩ B 1 ). Note that from the definition, . We claim that Y A ∩ Y B = ∅ and Y is anticomplete to Y B . Suppose not, then there is a path P in G[A ∪ B] from a vertex of A ∩ A 1 to a vertex of B ∩ B 1 . We may assume that P is minimal with respect to this property, and so the interior of P is in C 1 ; consequently it is of odd length because G(A ∪ B) is bipartite. This contradicts the assumption that (X 1 , X 2 ) is even. Now we set: From all the definitions and properties above, Z D and Z C are stable sets and Z D ⊆ X 1 and Z C ⊆ C 1 . So, α AC + α BC = w(Z C ) + w(Z D ) ≤ α C + α X .
The two lemmas above allow to construct blocks of decomposition of a 2-join that preserve being Berge and allow to keep track of α (see [28] for the precise definition of the blocks). Interestingly, 2-joins are used to compute α in other classes of graphs (while they seem to be hard to use in general): in claw-free graphs (see Faenza, Oriolo and Stauffer [45]), and in even-hole-free graphs with no star cutsets (see Trotignon and Vušković [96]).
In [28], the inequalities above are used to prove the following. Many technicalities are needed, and some of them come from the fact that the blocks of decomposition for 2-joins that keep track of α do not preserve being balanced-skew-partition-free. Also, it is proved in [28] that for Berge graphs with no balanced skew partition, there exist extreme decompositions, that are decompositions such that one of the block is basic. These are very convenient for proofs by induction. To handle all these technicalities, it is convenient (if not mandatory) to work with trigraphs, but here we state the result for graphs. There exists an O(n 7 ) time algorithm whose input is a Berge graph with no balanced skew partition and whose output is a maximum weighted stable set of G and a colouring of G.
So far, no one knows how skew partitions could be handled to provide a polynomial colouring algorithm. One might think that a Berge graph uniquely decomposable with a balanced skew partition must have an even pair. To support this idea, Chudnovsky and Seymour [25] studied the structure of Berge graphs with no K 4 and no even pair. They describe them quite precisely. Theorem 12.9 (Chudnovsky and Seymour 2012) If G is a 3connected K 4 -free Berge graph with no even pair, and with no clique cutset, then one of G, G is the line graph of a bipartite graph.
This theorem was generalized by Zwols [100] to {K 4 , odd holes}-free graphs (where non-perfect exceptions exist: C 7 , and a special graph on Figure 10: The WBGKSF (Worst Berge Graph Known So Far). Red (resp. green, blue) edges go to red (resp. green, blue) vertices. eleven vertices). Unfortunately, it seems that this theorem does not generalize to larger values of ω, as shown by the WBGKSF, a graph G (discovered by Chudnovsky and Seymour, unpublished) represented on Fig. 10. Every edge in G is the middle edge of a P 4 . This means that in the complement, every pair of non-adjacent vertices can be linked by a P 4 . Therefore, G has no even pairs. However, G is perfect, and the balanced skew partition is the only outcome of Theorem 6.1 satisfied by G. In fact, G has even pairs, so the next conjecture (unpublished) could still be true. It is quite challenging, but it is not clear whether it would help to colour perfect graphs because even pairs in the complement do not seem usable.
Conjecture 12.10 (Thomas, 2002) If a Berge graph G is uniquely decomposable by a balanced skew partitition (so G is not basic, has no 2-join and no complement 2-join), then one of G or G has an even pair.
I feel the next two questions as the most important ones about perfect graphs.
Question 12.11 Describe the structure of Berge graphs with no even pairs. Question 12.12 Describe a combinatorial polynomial time algorithm that colours every Berge graphs.