Recognizing bull-free perfect graphs (Q1895822)

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.