Sparse color-critical graphs and hypergraphs with no short cycles

✍ Scribed by H. L. Abbott; B. Zhou; D. R. Hare

• Publisher: John Wiley and Sons
• Year: 1994
• Tongue: English
• Weight: 709 KB
• Volume: 18
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190180408

✦ Synopsis

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.