Cycles in Triangle-free Graphs with Large Chromatic Number

Wednesday, September 10, 2014 - 2:00pm - 2:50pm
Keller 3-180
Alexandr Kostochka (University of Illinois at Urbana-Champaign)
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.
MSC Code: