Nie jesteś zalogowany | Zaloguj się

Minimum number of edges that occur in odd cycles

Prelegent(ci)
Andrzej Grzesik
Termin
24 listopada 2016 12:15
Pokój
p. 5870
Seminarium
Seminarium "Algorytmika"

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.