SPARSE COLOR-CRITICAL GRAPHS AND HYPERGRAPHS WITH NO SHORT CYCLES

We give constructions of color-critical graphs and hypergraphs with no short cycles and with relatively few edges. In particular, we show th at, for each n greater-than-or-equal-to 3, the smallest number of edge s in a 3-critical triangle-free n-graph (hypergraph) with m vertices i s m + o(m) as m --> infinity. Also, for each r greater-than-or-equal-t o 4, there exists an r-critical triangle-free 2-graph (graph) with m v ertices and at most (r - (7/3))m + o(m) edges. Weaker results are obta ined for the existence of r-critical graphs containing no cycle of len gth at most l > 3. (C) 1994 John Wiley & Sons, Inc.