ON THE ASYMPTOTIC STRUCTURE OF SPARSE TRIANGLE-FREE GRAPHS

An important result of Erdos, Kleitman, and Rothschild says that almos t every triangle-free graph on n vertices has chromatic number 2. In t his paper we study the asymptotic structure of graphs in Forb(n,m)(K-3 ), i.e., in the class of triangle-free graphs on n vertices having m = m(n) edges. In particular we prove that an analogue to the Erdos-Klei tman-Rothschild result is true, whenever m greater than or equal to cn (7/4) log n for some constant c > 0. On the other hand, it is shown th at almost every graph in Forb(n,m)(K-3) has at least chromatic number 3, provided that c(1)n < m < c(2)n(3/2), where c(1), c(2) > 0 are appr opriate constants. (C) 1996 John Wiley & Sons, Inc.