Erdos conjectured that a triangle-free graph with chromatic number k contains cycles of almost quadratically many different lengths, as k tends to infinity. We prove a somewhat stronger inequality for the number of consecutive lengths of cycles in k-chromatic graphs. The bound has the best possible order of magnitude because of Kim's construction of ``small'' triangle-free graphs with chromatic number k. We also give new lower bounds on the circumference and the number of different cycle lengths for k-chromatic graphs in other monotone classes, in particular, for graphs with bounded clique number and for graphs without odd cycles of a given length. This is joint work with Benny Sudakov and Jacques Verstraete.