Counterexamples to three conjectures concerning perfect graphs
A graph is perfect if and only if for every induced subgraph \(H\) of \(G\) the chromatic number of \(H\) equals the size of a largest clique in \(H\). A graph is called Berge if neither \(G\) nor its complement contains an odd- length induced cycle of length greater than 3. The famous Strong Perfect Graph Conjecture states: A graph is perfect if and only if it is Berge. In search of a proof of this conjecture a large theory has developed and many related conjectures made. This paper represents counterexamples to three such conjectures, all somewhat technical. A graph is minimal imperfect if it is not perfect but all proper induced subgraph are perfect. An even pair in \(G\) is a pair of vertices such that all induced paths between them have even length. One of the conjectures is: If a graph contains an even pair then it has an even pair at distance two. If this conjecture were true, the strong perfect graph conjecture would follow. Another disproven conjecture is: Every Berge graph or its complement contains an even pair or a star-cutset or is the line graph of a bipartite graph.
- Some conjectures on perfect graphs
- On the perfect graph conjecture
- Two conjectures equivalent to the perfect graph conjecture
- Counterexamples to a conjecture on matching Kneser graphs
- A graph counterexample to Davies' conjecture
- scientific article; zbMATH DE number 3902680
- Proof of a conjecture on irredundance perfect graphs
- Equistarable graphs and counterexamples to three conjectures on equistable graphs
- scientific article; zbMATH DE number 3887731
- Counterexamples to Thomassen's conjecture on decomposition of cubic graphs
- A characterization of perfect graphs
- A fast algorithm for coloring Meyniel graphs
- A new property of critical imperfect graphs and some consequences
- A semi-strong perfect graph theorem
- Alternating orientation and alternating colouration of perfect graphs
- Coloring perfect \((K_ 4\)-e)-free graphs
- Erratum: Optimizing weakly triangulated graphs. [Graphs and Combinatorics 5, 339-349 (1989)]
- scientific article; zbMATH DE number 3168327 (Why is no real title available?)
- scientific article; zbMATH DE number 3172312 (Why is no real title available?)
- scientific article; zbMATH DE number 3526698 (Why is no real title available?)
- Perfectly orderable graphs are quasi-parity graphs: a short proof
- Star-cutsets and perfect graphs
- Transformations which Preserve Perfectness and H-Perfectness of Graphs
- Even pairs in Berge graphs
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- A new conjecture about minimal imperfect graphs
- Some properties of minimal imperfect graphs
- Counterexamples to a conjecture of Mader about cycles through specified vertices in n-edge-connected graphs
- Quasi-parity and perfect graphs
- Path parity and perfection
- Building counterexamples
- On a conjecture about uniquely colorable perfect graphs
- Elementary bipartite graphs and unique colourability
- A disproof of Henning's conjecture on irredundance perfect graphs
- Even pairs and prism corners in square-free Berge graphs
- Counterexamples to Thomassen's conjecture on decomposition of cubic graphs
- A recognition algorithm for simple-triangle graphs
- On the complexity of finding even pairs in planar perfect graphs
- scientific article; zbMATH DE number 4158667 (Why is no real title available?)
- Three-colourable perfect graphs without even pairs
- scientific article; zbMATH DE number 1933066 (Why is no real title available?)
- scientific article; zbMATH DE number 2073528 (Why is no real title available?)
- Some conjectures on perfect graphs
- scientific article; zbMATH DE number 2096444 (Why is no real title available?)
- A structural property of monsters
- The strong perfect graph theorem
- On a conjecture of Hoàng and Tu concerning perfectly orderable graphs
- Decomposing Berge graphs containing no proper wheel, long prism or their complements
This page was built for publication: Counterexamples to three conjectures concerning perfect graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686172)
