Some properties of minimal imperfect graphs

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

Chính T. Hoàng

Publication date: 14 January 1997

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

minimal imperfect graph; theorem of Meyniel; \(U\)-cut-set lemma; antitwins lemma; odd pair conjecture; three-pair lemma

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C38: Paths and cycles

05C15: Coloring of graphs and hypergraphs

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

Fast Skew Partition Recognition, The strong perfect graph conjecture: 40 years of attempts, and its resolution, On minimal imperfect graphs without induced \(P_5\), \(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

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