Abstract
A stable set in a graph is a set of pairwise non-adjacent vertices.
The stable set polytope of a graph on n vertices is the convex hull in Rn of the incidence vectors of each of its stable sets. Since computing the stable set is NP-Hard, it is not expected that the stable set polytope of a general graph admits a (roughly-speaking) "nice" "easily verifiable" set of defining inequalities. However, certain well-known graph classes such as perfect graphs have this property. In this talk we examine one such graph class called "t-perfect graphs" and show that graphs in this class are 200,000 colorable, answering a question of B. Shephard from 1995.
The proof relies largely on techniques from structural graph theory.
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. 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.
Joint work with: Maria Chudnovsky (Princeton), James Davies (Cambridge), Sang-il Oum (IBS DIMAG), Jane Tan (Oxford)
Available at: https://arxiv.org/abs/2412.17735
