Some properties of minimal imperfect graphs

DOI10.1016/0012-365X(95)00156-QzbMath0863.05055OpenAlexW2089618463MaRDI QIDQ1126292

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

minimal imperfect graphtheorem of Meyniel\(U\)-cut-set lemmaantitwins lemmaodd pair conjecturethree-pair lemma

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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