Longest Cycles in Graphs with Given Independence Number and Connectivity.

Combinatorics Seminar
Friday, February 25, 2011 - 15:05
1 hour (actually 50 minutes)
Skiles 006
University of Illinois at Urbana-Champaign
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.