Optimizing Bull-free Perfect Graphs

Celina M. H. de Figueiredo^{∗}  Frédéric Maffray^{†}

A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. Chvátal and Sbihi [1] showed that the Strong Perfect Graph Conjecture holds for bull-free graphs by defining a decomposition operation with respect to homogeneous pairs. Reed and Sbihi [3] gave a polynomialtime recognition algorithm for bull-free perfect graphs.

In this talk, we present a polynomial-time algorithm for solving the optimization problems: maximum weighted clique and minimum weighted colouring for bull-free perfect graphs.

Given a bull-free perfect graph with no homogeneous set, our solution considers four cases according to the existence of a hole or of an even antihole in the graph. In case the graph has no hole and no antihole, we have a weakly triangulated graph; solutions for the optimization problems are known in this case. In case the graph has an even hole and no antihole, we defined in [2] a decomposition which allowed us to exhibit a perfect order in this case. We can further exploit this decomposition to show that we actually have a comparability graph; both comparability and co-comparability graphs are well-studied classes of perfect graphs. In case the graph has an even hole and and even antihole, we show how to use Chvátal’s decomposition with respect to a special homogeneous pair to optimize.

References

[1] V. Chvátal and N. Sbihi. Bull-free Berge graphs are perfect. Graphs and Combinatorics, 3:127–139, 1987.

[2] C. M. H de Figueiredo, F. Maffray, and O. Porto. On the structure of bull-free perfect graphs. Graphs and Combinatorics, 13:31–55, 1997.

[3] B.A. Reed and N. Sbihi. Recognizing bull-free perfect graphs. Graphs and Combinatorics, 11:171–178, 1995.

∗Universidade Federal do Rio de Janeiro, Brazil. celina@cos.ufrj.br.

†Laboratoire Leibniz - IMAG, France. Frederic.Maffray@imag.fr.