Some properties of minimal imperfect graphs (Q1126292): Difference between revisions
From MaRDI portal
Latest revision as of 11:11, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some properties of minimal imperfect graphs |
scientific article |
Statements
Some properties of minimal imperfect graphs (English)
0 references
14 January 1997
0 references
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.
0 references
\(U\)-cut-set lemma
0 references
odd pair conjecture
0 references
minimal imperfect graph
0 references
three-pair lemma
0 references
antitwins lemma
0 references
theorem of Meyniel
0 references
0 references