Counterexamples to three conjectures concerning perfect graphs (Q686172)

A graph is perfect if and only if for every induced subgraph \(H\) of \(G\) the chromatic number of \(H\) equals the size of a largest clique in \(H\). A graph is called Berge if neither \(G\) nor its complement contains an odd- length induced cycle of length greater than 3. The famous Strong Perfect Graph Conjecture states: A graph is perfect if and only if it is Berge. In search of a proof of this conjecture a large theory has developed and many related conjectures made. This paper represents counterexamples to three such conjectures, all somewhat technical. A graph is minimal imperfect if it is not perfect but all proper induced subgraph are perfect. An even pair in \(G\) is a pair of vertices such that all induced paths between them have even length. One of the conjectures is: If a graph contains an even pair then it has an even pair at distance two. If this conjecture were true, the strong perfect graph conjecture would follow. Another disproven conjecture is: Every Berge graph or its complement contains an even pair or a star-cutset or is the line graph of a bipartite graph.