No label defined (Q3337488)
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 3869356
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3869356 |
Statements
1984
0 references
perfect graphs
0 references
perfect orders
0 references
strong perfect-graph conjecture
0 references
0 references
0 references
[For the entire collection see Zbl 0535.00030.] Recall that a graph is perfect iff the chromatic number of each induced subgraph of it equals the largest number of pairwise adjacent vertices in this subgraph. This paper surveys several results and problems on perfect graphs. The most famous problem mentioned is, of course, the strong perfect-graph conjecture; the only minimal imperfect graphs are the odd cycles with at least 5 vertices and their complements. Another interesting, computational problem is if the problem of deciding whether a given graph is perfect lies in NP.
0 references