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