Premium
Constructions of sparse uniform hypergraphs with high chromatic number
Author(s) -
Kostochka A.V.,
Rödl V.
Publication year - 2010
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20293
Subject(s) - combinatorics , mathematics , chromatic scale , girth (graph theory) , degree (music) , simple (philosophy) , upper and lower bounds , discrete mathematics , physics , mathematical analysis , philosophy , epistemology , acoustics
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 ⌈ r k r ‐1 ln k ⌉. This is only 4 r 2 ln k times greater than the lower bound by Erdős and Lovász (Colloquia Math Soc János Bolyai 10 (1973), 609–627) that holds for all hypergraphs (without restrictions on girth). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010