Almost all graphs with high girth and suitable density have high chromatic number

✍ Scribed by Deryk Osthus; Hans Jürgen Prömel; Anusch Taraz

• Publisher: John Wiley and Sons
• Year: 2001
• Tongue: English
• Weight: 85 KB
• Volume: 37
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.1017

✦ Synopsis

Abstract

Erdös proved that there exist graphs of arbitrarily high girth and arbitrarily high chromatic number. We give a different proof (but also using the probabilistic method) that also yields the following result on the typical asymptotic structure of graphs of high girth: for all ℓ ≥ 3 and k ∈ ℕ there exist constants C~1~ and C~2~ so that almost all graphs on n vertices and m edges whose girth is greater than ℓ have chromatic number at least k, provided that $C_{1}n,\leq, m,\leq, C_{2}n^{\ell /(\ell -1)}$. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 220–226, 2001