Some properties of minimal imperfect graphs

DOI10.1016/0012-365X(95)00156-QMaRDI QIDQ1126292zbMATH OpenOpenAlexFDO

Authors Chính T. Hoàng

Publication date 14 January 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(95)00156-q

zbMATH Keywords

\(U\)-cut-set lemmaantitwins lemmaminimal imperfect graphodd pair conjecturetheorem of Meynielthree-pair lemma

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Review text

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.

Recommendations

• A new conjecture about minimal imperfect graphs
• No antitwins in minimal imperfect graphs
• Counterexamples to three conjectures concerning perfect graphs
• Odd pairs of cliques

Cites work

• A new conjecture about minimal imperfect graphs
• A new property of critical imperfect graphs and some consequences
• A note on even pairs
• Anti-blocking polyhedra
• Bull-free Berge graphs are perfect
• Coloring perfect \((K_ 4\)-e)-free graphs
• Combinatorial designs related to the strong perfect graph conjecture
• Critical perfect graphs and perfect 3-chromatic graphs
• Erratum: Optimizing weakly triangulated graphs. [Graphs and Combinatorics 5, 339-349 (1989)]
• Graphical properties related to minimal imperfection
• scientific article; zbMATH DE number 3889583 (Why is no real title available?)
• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Meyniel graphs are strongly perfect
• New classes of Berge perfect graphs
• No antitwins in minimal imperfect graphs
• Normal hypergraphs and the perfect graph conjecture
• On a conjecture of Meyniel
• On the perfect graph conjecture
• On the sibling-structure of perfect graphs
• On the strong perfect graph conjecture
• Opposition graphs are strict quasi-parity graphs
• Perfect zero–one matrices
• Star-cutsets and perfect graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• The validity of the strong perfect-graph conjecture for (K₄-e)-free graphs
• Topics on perfect graphs
• Two classes of perfect graphs

Cited in

(15)

• The strong perfect graph conjecture: 40 years of attempts, and its resolution
• A new conjecture about minimal imperfect graphs
• No antitwins in minimal imperfect graphs
• On minimal imperfect graphs without induced P₅
• \(P_4\)-domination in minimal imperfect graphs
• Path parity and perfection
• Square-free perfect graphs.
• Quasi-star-cutsets and some consequences
• About skew partitions in minimal imperfect graphs
• No odd pairs in minimal imperfect NP\({}_{5}\) graphs.
• Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday)
• Skew partitions in perfect graphs
• Some aspects of minimal imperfect graphs
• Colouring perfect graphs with bounded clique number
• Fast Skew Partition Recognition

This page was built for publication: Some properties of minimal imperfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1126292)