11.11.2025 16:00 Matija Novakovic:
t-perfect graphs are 199,053-colorableMI 02.06.011 (Boltzmannstr. 3, 85748 Garching)
A graph is perfect if and only if its stable set polytope is equal to its associated QSTAB polytope, defined via clique inequalities. In 1975, Chvátal defined the analogous class of t-perfect graphs, which replaces the clique inequalities with certain odd-circuit inequalities. In 1994, Shepherd conjectured that the chromatic number of a t-perfect graph is at most 4. In 2024, Chudnovsky, Cook, Davies, Oum, and Tan have shown the first finite upper bound of 199,053.
This talk discusses their proof, how their bound arises, and why they believe that it can be considerably improved.