A 200,000 colour theorem

The seminar series covers topics in Algebra and Topology

schedule Date & time
Date/time
30 Sep 2025 3:00pm - 30 Sep 2025 4:00pm
person Speaker

Speakers

Jane Tan (All Souls College, Oxford)
next_week Event series
contact_support Contact

Content navigation

Description

Abstract:

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 been 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.

Location

Room 1.33, Hanna Neumann Building #145

-35.275496166062, 149.1193313593

Upcoming events in this series

Topology
23 Sep 2025 | 3 - 4pm

The seminar series covers topics in Algebra and Topology

View the event