A proof of the Erdős–Faber–Lovász conjecture

Dong Yeap Kang; Tom Kelly; Daniela Kühn; Abhishek Methuku; Deryk Osthus

doi:https://doi.org/10.4007/annals.2023.198.2.2

A proof of the Erdős–Faber–Lovász conjecture

Pages 537-618 from Volume 198 (2023), Issue 2 by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, Deryk Osthus

Abstract

The Erdős–Faber–Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. In this paper, we prove this conjecture for every large $n$. We also provide stability versions of this result, which confirm a prediction of Kahn.

Keywords

absorption, chromatic index, graph coloring, hypergraph edge coloring, nibble

Mathematical Subject Classification

Primary 2000: 05C15, 05C65, 05D40

DOI

https://doi.org/10.4007/annals.2023.198.2.2

4635300

zbMATH

07734887

Milestones

Received: 12 January 2021
Revised: 22 July 2022
Accepted: 19 January 2023
Published online: 31 August 2023