| Abstract: | We give constructions of color-critical graphs and hypergraphs with no short cycles and with relatively few edges. In particular, we show that, for each n ≧ 3, the smallest number of edges in a 3-critical triangle-free n-graph (hypergraph) with m vertices is m + o(m) as m → ∞. Also, for each r ≧ 4, there exists an r-critical triangle-free 2-graph (graph) with m vertices and at most (r ? (7/3))m + o(m) edges. Weaker results are obtained for the existence of r-critical graphs containing no cycle of length at most / > 3. |
