Dense uniform hypergraphs have high list chromatic number

Noga Alon, Alexandr Kostochka

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

The first author showed that the list chromatic number of every graph with average degree d is at least (0.5-o(1))log2d. We prove that for r<3, every r-uniform hypergraph in which at least half of the (r-1)-vertex subsets are contained in at least d edges has list chromatic number at least lnd100r3. When r is fixed, this is sharp up to a constant factor.

Original languageEnglish (US)
Pages (from-to)2119-2125
Number of pages7
JournalDiscrete Mathematics
Volume312
Issue number14
DOIs
StatePublished - Jul 28 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • Co-degree
  • Hypergraph
  • List coloring

Fingerprint Dive into the research topics of 'Dense uniform hypergraphs have high list chromatic number'. Together they form a unique fingerprint.

Cite this