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 language | English (US) |
---|---|
Pages (from-to) | 46-56 |
Number of pages | 11 |
Journal | Random Structures and Algorithms |
Volume | 36 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2010 |
Keywords
- Girth
- Hypergraph coloring
- Simple hypergraphs
ASJC Scopus subject areas
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics