Longest Cycles in Graphs with Given Independence Number and Connectivity.

Series
Combinatorics Seminar
Time
Friday, February 25, 2011 - 3:05pm for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Hehui Wu – University of Illinois at Urbana-Champaign
Organizer
Xingxing Yu
The Chv\'atal--Erd\H{o}s Theorem states that every graph whose connectivityis at least its independence number has a spanning cycle. In 1976, Fouquet andJolivet conjectured an extension: If $G$ is an $n$-vertex $k$-connectedgraph with independence number $a$, and $a \ge k$, then $G$ has a cycle of lengthat least $\frac{k(n+a-k)}{a}$. We prove this conjecture. This is joint work with Suil O and Douglas B. West.