Constructions of sparse uniform hypergraphs with high chromatic number

A. V. Kostochka, V. Rödl

Research output: Contribution to journalArticlepeer-review

Abstract

A random construction gives new examples of simple hyper graphs with high chromatic number that have few edges and/ or low maximum degree. In particular, for every integer sk ≥ 2,r ≥ 2, and g ≥ 3, there exist r-uniform non-k-colorable hypergraphs of girth at least g with maximum degree at most ⌈r kr-1 ln k⌉. This is only 4r2 ln k times greater than the lower bound by Erdos and Lovász (Colloquia Math Soc János Bolyai 10 (1973), 609-627) that holds for all hypergraphs (without restrictions on girth).

Original languageEnglish (US)
Pages (from-to)46-56
Number of pages11
JournalRandom Structures and Algorithms
Volume36
Issue number1
DOIs
StatePublished - Jan 2010

Keywords

  • Girth
  • Hypergraph coloring
  • Simple hypergraphs

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Constructions of sparse uniform hypergraphs with high chromatic number'. Together they form a unique fingerprint.

Cite this