Minimum number of edges that occur in odd cycles

Speaker(s)

Andrzej Grzesik

Date

Nov. 24, 2016, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

For any fixed k>1 every graph without a cycle on 2k+1 vertices has at most n^2/4 edges. In 1992, Erdos, Faudree and Rousseau conjectured that if a graph has at least n^2/4 + 1 edges, then already at least 2n^2/9 edges occur in cycles on 2k+1 vertices. In the talk I will disprove this conjecture for k=2 and prove the exact bound for every k>1.

---