Recognizing bull-free perfect graphs (Q1895822): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3222886 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Star-cutsets and perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bull-free Berge graphs are perfect / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On rigid circuit graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3328583 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The ellipsoid method and its consequences in combinatorial optimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Weakly triangulated graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Normal hypergraphs and the perfect graph conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a property of the class of n-colorable graphs / rank | |||
Normal rank |
Latest revision as of 16:07, 23 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Recognizing bull-free perfect graphs |
scientific article |
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