Seminar series
Date
Tue, 22 Nov 2016
14:30
14:30
Location
L6
Speaker
Paul Seymour
Organisation
Princeton University
It follows from the ellipsoid method and results of Grotschel, Lovasz and Schrijver that one can find an optimal colouring of a perfect graph in polynomial time. But no ''combinatorial'' algorithm to do this is known.
Here we give a combinatorial algorithm to do this in an n-vertex perfect graph in time O(n^{k+1}^2) where k is the clique number; so polynomial-time for fixed k. The algorithm depends on another result, a polynomial-time algorithm to find a ''balanced skew partition'' in a perfect graph if there is one.
Joint work with Maria Chudnovsky, Aurelie Lagoutte, and Sophie Spirkl.