No antitwins in minimal imperfect graphs

DOI10.1016/0095-8956(88)90071-8MaRDI QIDQ1107542zbMATH OpenOpenAlexFDO

Authors Stephan Olariu

Publication date 1988

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://digitalcommons.odu.edu/cgi/viewcontent.cgi?article=1110&context=computerscience_fac_pubs

zbMATH Keywords

antitwinsminimal imperfect graphtwins

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99)

Review text

A graph G is perfect if for every induced subgraph H of G, the chromatic number of H equals the largest number of pairwise adjacent vertices in H. The vertices x and y are twins and antitwins if every vertex distinct from x and y is adjacent either to both of them or to neither of them and to precisely one of them respectively. A graph G is minimal imperfect if G itself is imperfect but every proper induced subgraph of G is perfect. Lovász proved that no minimal imperfect graph has twins. The author proves that no minimal imperfect graph contains antitwins.

Recommendations

• Some properties of minimal imperfect graphs
• On critical edges in minimal imperfect graphs
• On the strong perfect graph conjecture
• A new property of critical imperfect graphs and some consequences
• Minimal imperfect graphs: A simple approach

Cites work

• scientific article; zbMATH DE number 3885919 (Why is no real title available?)
• Normal hypergraphs and the perfect graph conjecture
• Perfect zero–one matrices

Cited in

(9)

• Bull-free Berge graphs are perfect
• Wings and perfect graphs
• Some properties of minimal imperfect graphs
• Antitwins in partitionable graphs
• \(P_4\)-domination in minimal imperfect graphs
• New classes of Berge perfect graphs
• Path parity and perfection
• Completeness for intersection classes
• No odd pairs in minimal imperfect NP\({}_{5}\) graphs.

This page was built for publication: No antitwins in minimal imperfect graphs

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