On the structure of bull-free perfect graphs (Q675887)

An even pair of a graph is any pair of vertices such that every chordless path between them has even length. A graph is called a quasi-parity graph if every non-trivial induced subgraph either has an even pair or its complement has an even pair. \textit{H. Meyniel} proved that every quasi-parity graph is perfect [Eur. J. Comb. 8, 313-316 (1987; Zbl 0647.05053)]. Given a graph \(G\) and an even pair \(x\), \(y\) of \(G\), the contraction of the two vertices \(x\), \(y\) is denoted by \(G/xy\). A graph is called perfectly contractile if for every induced subgraph \(H\) there exists a sequence \(H_{0},\ldots ,H_{p}\) of graphs such that: \(H=H_{0}\); \(H_{i}\) has an even pair \(x_{i}\), \(y_{i}\) for \(i=0,\ldots ,p-1\); \(H_{i+1}=H_{i}/x_{i}y_{i}\); and \(H_{p}\) is a clique. A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. \textit{V. Chvátal} and \textit{N. Sbihi} showed that the strong perfect graph conjecture holds for bull-free graphs [Graph. Comb. 3, 127-139 (1987; Zbl 0633.05056)]. In this paper it is shown that bull-free perfect graphs are quasi-parity graphs, and that bull-free perfect graphs with no antihole are perfectly contractile. The proof yields a polynomial algorithm for coloring bull-free strict quasi-parity graphs with \(n\) vertices and \(m\) edges with complexity \(O(n^{4}m)\). Some conjectures and open problems conclude the paper.