Wednesday, September 10, 2014 - 2:00pm - 2:50pm
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
Subscribe to RSS - Cycle