Coloring hypergraphs of small codegree, and a proof of the Erdős–Faber–Lovász conjecture
- Job Candidate Talk
- Thursday, January 20, 2022 - 11:00 for 1 hour (actually 50 minutes)
- Thomas Kelly – University of Birmingham – T.J.Kelly@bham.ac.uk
Meeting link: https://bluejeans.com/961048334/8189
A long-standing problem in the field of graph coloring is the Erdős–Faber–Lovász conjecture (posed in 1972), which states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$, or equivalently, that a nearly disjoint union of $n$ complete graphs on at most $n$ vertices has chromatic number at most $n$. In joint work with Dong Yeap Kang, Daniela Kühn, Abhishek Methuku, and Deryk Osthus, we proved this conjecture for every sufficiently large $n$. Recently, we also solved a related problem of Erdős from 1977 on the chromatic index of hypergraphs of small codegree. In this talk, I will survey the history behind these results and discuss some aspects of the proofs.