Recognizing bull-free perfect graphs
type: Item
instance of: scholarly article
title: Recognizing bull-free perfect graphs
zbMATH Open document ID: 0832.05039
DOI: 10.1007/BF01929485
author: Najiba Sbihi
author: Bruce Reed
published in: Graphs and Combinatorics
publication date: 1996-02-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 784145
zbMATH Keywords: bull
zbMATH Keywords: chromatic number
zbMATH Keywords: strong perfect graph conjecture
zbMATH Keywords: recognition algorithm
zbMATH Keywords: bull-free perfect graphs
Wikidata QID: Q64012590
reviewed by: Marek Kubale
MaRDI profile type: Publication
cites work: Q3222886
cites work: Star-cutsets and perfect graphs
cites work: Bull-free Berge graphs are perfect
cites work: On rigid circuit graphs
cites work: Q3328583
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Weakly triangulated graphs
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: On a property of the class of n-colorable graphs
Recommended article: The structure of bull-free perfect graphs
Recommended article: On the structure of bull-free perfect graphs
Recommended article: The perfection and recognition of bull-reducible Berge graphs
Recommended article: Bull-free Berge graphs are perfect
Recommended article: Coloring Bull-Free Perfect Graphs
Recommended article: Optimizing Bull-Free Perfect Graphs
Recommended article: Recognizing claw-free perfect graphs
Recommended article: Q4952598
Recommended article: Recognizing Dart-Free Perfect Graphs
Recommended article: Q4871157
description: scientific article; zbMATH DE number 784145