Constructions of Sparse Uniform Hypergraphs With High Chromatic Number
A random construction gives new examples of simple hypergraphs with high chromatic number that have few edges and/or low maximum degree. In particular, for every integers k >= 2, r >= 2, and g >= 3, there exist r-uniform non-k-colorable hypergraphs of girth at least g with maximum degree at most inverted right perpendicular r k(r-1) In k inverted left perpendicular. This is only 4r(2) Ink times greater than the lower bound by Erdos and Lovasz (Colloquia Math Soc Janos Bolyai 10 (1973), 609-627) that holds for all hypergraphs (without restrictions on girth). (C) 2009 Wiley Periodicals, Inc. Random Struct. Alg., 36, 46-56, 2010
simple hypergraphs girth hypergraph coloring