Abstract

Perfect graphs can be described as the graphs whose stable set polytopes are defined by their non-negativity and clique inequalities. In 1975, V. Chvátal defined an analogous class called t-perfect graphs, which are the graphs whose stable set polytopes are defined by their non-negativity, edge inequalities, and odd circuit inequalities. We show that t-perfect graphs are 200,000-colourable. This is the first finite bound on the chromatic number of t-perfect graphs, and answers a question of B. Shepherd from 1995.

This bound is probably not tight;  M. Laurent and P. Seymour gave an example of a t-perfect graph requiring four colors in the 1990's and it is open whether all t-perfect graphs are 4-colorable. Our proof is mainly graph theoretic.

Joint work with: Maria Chudnovsky (Princeton), James Davies (Cambridge), Sang-il Oum (IBS DIMAG), Jane Tan (Oxford)