# Trees in greedy colorings of hypergraphs

- Authors
- Journal
- Discrete Mathematics 0012-365X
- Publisher
- Elsevier
- Volume
- 311
- Identifiers
- DOI: 10.1016/j.disc.2010.10.017
- Keywords
- Disciplines

## Abstract

Abstract It is a well-known proposition that every graph of chromatic number larger than t contains every tree with t edges. The ‘standard’ reasoning is that such a graph must contain a subgraph of minimum degree at least t . Bohman, Frieze and Mubayi noticed that although this argument does not work for hypergraphs, it is still possible that the proposition holds for hypergraphs as well. Indeed, Po-Shen Loh recently proved that every uniform hypergraph of chromatic number larger than t contains every hypertree with t edges. Here we observe that the basic property of the well-known greedy algorithm implies immediately a much more general result (with a conceptually simpler proof): if the greedy algorithm colors the vertices of an r -uniform hypergraph with more than t colors then the hypergraph contains every r -uniform hypertree with t edges.

## There are no comments yet on this publication. Be the first to share your thoughts.