Coloring uniform hypergraphs with few edges

A. V. Kostochka, M. Kumbhat

Research output: Contribution to journalArticle

Abstract

A hypergraph is b-simple if no two distinct edges share more than b vertices. Let m(r,t,g) denote the minimum number of edges in an r-uniform non-t-colorable hypergraph of girth at least g. Erdo{double acute}s and Lovász proved that A result of Szabó improves the lower bound by a factor of r2-ε for sufficiently large r. We improve the lower bound by another factor of r and extend the result to b-simple hypergraphs. We also get a new lower bound for hypergraphs with a given girth. Our results imply that for fixed b,t, and ε > 0 and sufficiently large r, every r-uniform b-simple hypergraph H with maximum edge-degree at most trr1-ε is t-colorable. Some results hold for list coloring, as well.

Original languageEnglish (US)
Pages (from-to)348-368
Number of pages21
JournalRandom Structures and Algorithms
Volume35
Issue number3
DOIs
StatePublished - Oct 1 2009

Keywords

  • Edge-degree
  • Hypergraph coloring
  • Maximum degree
  • Small size

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Coloring uniform hypergraphs with few edges'. Together they form a unique fingerprint.

  • Cite this