No label defined (Q3222219)
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 3887724
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3887724 |
Statements
1984
0 references
strong perfect graph conjecture
0 references
toroidal graphs
0 references
0.8542443513870239
0 references
0.8534672260284424
0 references
0.8530899286270142
0 references
0.8416175246238708
0 references
[For the entire collection see Zbl 0546.00006.] A graph G is perfect if for each (vertex-induced) subgraph H\b{c}G, the chromatic number of H equals the size of the largest clique in H. The strong perfect graph conjecture due to C. Berge, states that a graph is perfect if and only if neither G nor its complement \(\bar G\) contain an odd hole (an odd hole is an odd chordless cycle of length at least five). This article shows that the strong perfect graph conjecture is valid for toroidal graphs, graphs that can be embedded on the surface of a torus. The proof relies on the fact that one can assume that if the largest clique is \(\geq\) then the toroidal graph is regular of degree six and triangulates the torus.
0 references