## 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 r^{2-ε} 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 t^{r}r^{1-ε} is t-colorable. Some results hold for list coloring, as well.

Original language | English (US) |
---|---|

Pages (from-to) | 348-368 |

Number of pages | 21 |

Journal | Random Structures and Algorithms |

Volume | 35 |

Issue number | 3 |

DOIs | |

State | Published - Oct 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