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

theorem of Meynielminimal imperfect graph\(U\)-cut-set lemmaantitwins lemmaodd pair conjecturethree-pair lemma

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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)

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

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)