Séminaire

Perfect graphs are graphs for which the chromatic number matches the trivial lower bound consisting in the clique number (and the same holds for every induced subgraph). After the long study that led to the Strong Perfect Graph Theorem, the main open question concerning them is about finding an optimal coloring with a combinatorial algorithm. Indeed, deciding if the chromatic number of a graph is at most k is NP-complete in general, and even if k=3. A famous result of Lovasz, Grötchel and Schrijver provides a polynomial-time algorithm that optimally colors any perfect graph, however this algorithm uses the ellipsoid method which makes it unpractical and not combinatorial. We design a purely combinatorial algorithm that, given in input a perfect graph, outputs an optimal coloring in time O(n^f) where f is quadratic in the clique number omega(G). This is joint work with Maria Chudnovsky, Paul Seymour and Sophie Spirkl.