Some properties of minimal imperfect graphs
From MaRDI portal
Publication:1126292
DOI10.1016/0012-365X(95)00156-QzbMath0863.05055MaRDI QIDQ1126292
Publication date: 14 January 1997
Published in: Discrete Mathematics (Search for Journal in Brave)
minimal imperfect graph; theorem of Meyniel; \(U\)-cut-set lemma; antitwins lemma; odd pair conjecture; three-pair lemma
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, Colouring perfect graphs with bounded clique number, 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