| A trigraph T is a complete graph with the edge set partitioned into three sets: strong edges, strong non-edges and switchable edges . A trigraph is Berge if for every subset S of switchable edges the graph G whose edge set is the union of S with the set of all strong edges of T is Berge.; We prove the following result for Berge trigraphs: The decomposition result of [2] for Berge graphs extends (with slight modifications) to trigraphs i.e. either T belongs to one of a few basic classes or T has a decomposition, where all the "important" edges and non-edges in the decomposition are strong edges and strong non-edges of T respectively.; In the proof of the Strong Perfect Graph Theorem we used three kinds of decompositions: skew-partitions, 2-joins and M-joins. The result about Berge trigraphs implies that the M-join decomposition is in fact unnecessary.; Another consequence of the result about Berge trigraphs is the following: if G is a Berge graph then either it belongs to one of a few basic classes, or it admits a skew partition or an M-join, or it admits a 2-join so that neither half of it is just an induced path, or the complement of G admits a 2-join. |
