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

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

doi:10.4007/annals.2023.198.2.2

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

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

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	537-618
Number of pages	82
Journal	Annals of Mathematics
Volume	198
Issue number	2
DOIs	https://doi.org/10.4007/annals.2023.198.2.2
State	Published - 2023
Externally published	Yes

Keywords

absorption AMS Classification: Primary: 05C15, 05C65, 05D40
chromatic index
graph coloring
hypergraph edge coloring
nibble

ASJC Scopus subject areas

Mathematics (miscellaneous)

Online availability

10.4007/annals.2023.198.2.2

Library availability

Discover UIUC Full Text

Cite this

@article{8d69edc2468f485194509f3d2dd78cf4,

title = "A proof of the Erd{\H o}s—Faber—Lov{\'a}sz conjecture",

abstract = "The Erd{\H o}s—Faber—Lov{\'a}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 AMS Classification: Primary: 05C15, 05C65, 05D40, chromatic index, graph coloring, hypergraph edge coloring, nibble",

author = "Kang, {Dong Yeap} and Tom Kelly and Daniela K{\"u}hn and Abhishek Methuku and Deryk Osthus",

note = "Publisher Copyright: {\textcopyright} 2023 Department of Mathematics, Princeton University",

year = "2023",

doi = "10.4007/annals.2023.198.2.2",

language = "English (US)",

volume = "198",

pages = "537--618",

journal = "Annals of Mathematics",

issn = "0003-486X",

publisher = "Department of Mathematics at Princeton University",

number = "2",

}

TY - JOUR

T1 - A proof of the Erdős—Faber—Lovász conjecture

AU - Kang, Dong Yeap

AU - Kelly, Tom

AU - Kühn, Daniela

AU - Methuku, Abhishek

AU - Osthus, Deryk

PY - 2023

Y1 - 2023

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

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

KW - absorption AMS Classification: Primary: 05C15, 05C65, 05D40

KW - chromatic index

KW - graph coloring

KW - hypergraph edge coloring

KW - nibble

UR - http://www.scopus.com/inward/record.url?scp=85171304074&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85171304074&partnerID=8YFLogxK

U2 - 10.4007/annals.2023.198.2.2

DO - 10.4007/annals.2023.198.2.2

M3 - Article

AN - SCOPUS:85171304074

SN - 0003-486X

VL - 198

SP - 537

EP - 618

JO - Annals of Mathematics

JF - Annals of Mathematics

IS - 2

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this