Coloring uniform hypergraphs with small edge degrees

Alexandr V. Kostochka, Mohit Kumbhat, Vojtěch Rödl

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

Abstract

Let k be a positive integer and n = [log2 k] We prove that there is an ε = ε(k) > 0 such that for sufficiently large r, every r-uniform hypergraph with maximum edge degree at most ε(k)k r(r/In r)n/n+1 is k-colorable.

Original languageEnglish (US)
Title of host publicationFete of Combinatorics and Computer Science
Pages213-238
Number of pages26
DOIs
StatePublished - 2010
EventMeeting on Fete of Combinatorics and Computer Science - Keszthely, Hungary
Duration: Aug 11 2008Aug 15 2008

Publication series

NameBolyai Society Mathematical Studies
Volume20
ISSN (Print)1217-4696
ISSN (Electronic)1217-4696

Other

OtherMeeting on Fete of Combinatorics and Computer Science
Country/TerritoryHungary
CityKeszthely
Period8/11/088/15/08

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Coloring uniform hypergraphs with small edge degrees'. Together they form a unique fingerprint.

Cite this