# 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.

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:

05C38