Stability number of bull- and chair-free graphs revisited (Q1408811)

The authors regard finite undirected graphs without self-loops and multiple edges. A bull is a graph with vertices \(a,b,c,d,e\) and edges \(ab,bc,cd,be,ce\); a chair is a graph with vertices \(a,b,c,d,e\) and edges \(ab,bc,cd,be\); and a diamond is \(K_4\) minus one edge. Given a graph \(G\) the co-\(G\) is the complement of \(G\). By a subgraph it is meant an induced subgraph. \textit{C. De Simone} [Graphs Comb. 9, 19-30 (1993; Zbl 0781.05041)] studied a class of graphs, called prime graphs, and showed that prime bull- and chair-free graphs containing a co-diamond are either bipartite or a cycle of length at least 5. Based on this result, the authors give a complete structural characterization of prime (bull, chair)-free graphs having stability number at least four as well as of (bull, chair, co-chair)-free graphs. This implies constant-bounded clique width for these graph classes and leads to effective algorithms for some algorithmic problems.