Some properties of minimal imperfect graphs (Q1126292): Difference between revisions

Two vertices \(x,y\) of a graph \(G\) form an odd pair if all chordless \(x\)--\(y\) paths of \(G-xy\) have an odd number of edges. The odd pair conjecture that no minimal imperfect graph contains an odd pair is an important unsolved problem in perfect graph theory. The main result of the present paper is the three-pair lemma that no minimal imperfect graph contains a three-pair. The author proves this using Olariu's antitwins lemma saying that no minimal imperfect graph contains antitwins (a pair of vertices \(x\), \(y\) of a graph \(G\) such that each vertex of \(G-xy\) is adjacent to precisely one vertex of \(x,y)\), and a \(U\)-cut-set lemma, based on the concept of Chvátal's `skew partition'. The above techniques enable the author to prove generalizations of a theorem of Meyniel and one of Olariu.