Optimizing Bull-Free Perfect Graphs
Celina M.H. de Figueiredo, Frédéric Maffray · SIAM Journal on Discrete Mathematics · 2004
A bull is a graph with five vertices a,b,c,d,e and five edges ab, ac, bc, da, eb. Here we present polynomial-time combinatorial algorithms for the optimal weighted coloring and weighted clique problems in bull-free perfect graphs. The algorithms are based on a structural analysis and decomposition of bull-free perfect graphs.