General Math Colloquium: Linda Cook
200,000 colors suffice (for t-perfect graphs)
Our next meeting of the General Mathematics Colloquium series at the Korteweg-de Vries Institute for Mathematics will be Wednesday, November 6 at 16.00. Linda Cook will speak about colouring graphs with many (but not more than 200000) colours.
Event details from: General Math Colloquium: Linda Cook
- Date
- 6 November 2024
- Time
- 16:00
- Room
- F3.20
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)
