Coloring perfect graphs with bounded clique number

Coloring perfect graphs with bounded clique number

-
Sophie Spirkl , Princeton University
Fine Hall 224

I will talk about optimally coloring Berge graphs (graphs with no odd hole or antihole). The main difficulty with finding a combinatorial algorithm is handling decompositions by balanced skew partitions. I will show how to solve this in the case of bounded clique number.  Joint with with Maria Chudnovsky, Aurelie Lagoutte and Paul Seymour.