Almost all graphs with high girth and suitable density have high chromaticnumber

Erdos proved that there exist graphs of arbitrarily high girth and arbitrar ily high chromatic number. We give a different proof (but also using the pr obabilistic method) that also yields the following result on the typical as ymptotic structure of graphs of high girth: for all e greater than or equal to 3 and k epsilon N there exist constants C-1 and C-2 so that almost all graphs on n vertices and m edges whose girth is greater than e have chromat ic number at least k, provided that C(1)n less than or equal to m less than or equal to C(2)n(e/(e-1)). (C) 2001 John Wiley & Sons, Inc.