Recognizing bull-free perfect graphs (Q1895822)
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 784145
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Recognizing bull-free perfect graphs |
scientific article; zbMATH DE number 784145 |
Statements
Recognizing bull-free perfect graphs (English)
0 references
20 February 1996
0 references
A bull is the graph obtained from a triangle by adding two pendant vertices adjacent to distinct vertices of the triangle. A graph is perfect if for any induced subgraph \(G'\) of \(G\) the clique and chromatic number of \(G'\) are equal. In 1987, Chvátal and Sbihi showed that the strong perfect graph conjecture holds for bull-free graphs. In this paper the authors give an \(O(n^5)\)-time recognition algorithm for bull-free perfect graphs, where \(n\) is the order of \(G\). Note that the general perfect graph recognition problem is in class co-NP.
0 references
bull
0 references
chromatic number
0 references
strong perfect graph conjecture
0 references
recognition algorithm
0 references
bull-free perfect graphs
0 references
0.9359018
0 references
0.93499947
0 references
0.9094074
0 references
0 references
0 references
0 references
0 references
0 references
