MATH Seminar

Title: Coloring hypergraphs of small codegree, and a proof of the Erdős–Faber–Lovász conjecture
Seminar: Discrete Mathematics
Speaker: Tom Kelly of The University of Birmingham
Contact: Dwight Duffus, dwightduffus@emory.edu
Date: 2022-01-19 at 10:00AM
Venue: Zoom
Download Flyer
Abstract: A long-standing problem in the field of graph coloring is the Erd$\ddot{\mathrm{o}}$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$\ddot{\mathrm{o}}$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.