No label defined (Q3688409)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3910416
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3910416 |
Statements
1984
0 references
Strong Perfect Graph Conjecture
0 references
circle graph
0 references
SPGC
0 references
0.8747860193252563
0 references
0.867185652256012
0 references
0.867185652256012
0 references
0.8622435331344604
0 references
[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).
0 references