A proof of the Erdös-Faber-Lovász conjecture: algorithmic aspects

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The Erdos-Faber-Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. Erdös considered this to be one of his three most favorite combinatorial problems and offered a 500 reward for a proof of this conjecture. We prove this conjecture for every large n. Here, we also provide a randomised algorithm to find such a colouring in polynomial time with high probability.

Original languageEnglish
Title of host publication2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
PublisherIEEE Computer Society Press
Pages1080-1089
Number of pages10
ISBN (Electronic)9781665420556
ISBN (Print)9781665420563 (PoD)
DOIs
Publication statusPublished - 4 Mar 2022
Event62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 - Virtual, Online, United States
Duration: 7 Feb 202210 Feb 2022

Publication series

NameAnnual IEEE Symposium on Foundations of Computer Science
ISSN (Print)1523-8288
ISSN (Electronic)2575-8454

Conference

Conference62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021
Country/TerritoryUnited States
CityVirtual, Online
Period7/02/2210/02/22

Bibliographical note

Publisher Copyright:
© 2022 IEEE.

Keywords

  • Erdös-Faber-Lovász
  • Hypergraph colouring
  • Rödl nibble

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'A proof of the Erdös-Faber-Lovász conjecture: algorithmic aspects'. Together they form a unique fingerprint.

Cite this