scientific article; zbMATH DE number 3910416
[For the entire collection see Zbl 0549.00001.] The Strong Perfect Graph Conjecture states that a graph G is perfect (i.e. the chromatic number of any induced subgraph H equals the size of the largest clique in H) if and only if neither G nor its complement contains a cycle of odd length without diagonals. A circle graph is a graph whose vertices may be put into one-to-one correspondence with the chords of a circle, such that two vertices are adjacent if and only if their corresponding chords intersect. In this work we will prove the SPGC is true for the class of circle graphs. An alternative proof is to be found in the first author's doctoral thesis (New York University, 1981; Courant Computer Science Report No.21, October, 1980).
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- The strong perfect graph conjecture holds for diamonded odd cycle-free graphs
- Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture
- Two conjectures equivalent to the perfect graph conjecture
- A survey of the strong perfect graph conjecture and some recent results
- scientific article; zbMATH DE number 3885936 (Why is no real title available?)
- Families of graphs complete for the strong perfect graph Conjecture
- scientific article; zbMATH DE number 1295365 (Why is no real title available?)
- scientific article; zbMATH DE number 1009511 (Why is no real title available?)
- On Tucker's proof of the strong perfect graph conjecture for \((K_4-e)\)-free graphs
- The edge intersection graphs of paths in a tree
- On circular critical graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3688409)