Jane Tan

A 200000-colour theorem

The class of $t$-perfect graphs consists of graphs whose stable set polytopes are defined by their non-negativity, edge inequalities, and odd circuit inequalities. These were first studied by Chv/‘atal in 1975, motivated by the related and well-studied class of perfect graphs. While perfect graphs are easy to colour, the same is not true for $t$-perfect graphs; numerous questions and conjectures have been posed, and even the most basic, on whether there exists some $k$ such that every $t$-perfect graph is $k$-colourable, has remained open since 1994. I will talk about joint work with Maria Chudnovsky, Linda Cook, James Davies, and Sang-il Oum in which we establish the first finite bound and show that a little less than 200 000 colours suffice.