W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Mathematics Colloquium/CSUMS Lecture: Hehui Wu (McGill University, Canada)
September 23, 2011
2pm - 3pm
Abstract:
The Chv\'atal--Erd\H{o}s Theorem states that every graph whose connectivity is at least its independence number has a spanning cycle. In 1976, Fouquet and Jolivet conjectured an extension: If $G$ is an $n$-vertex $k$-connected graph with independence number $a$, and $a \ge k$, then $G$ has a cycle of length at least $\frac{k(n+a-k)}{a}$. We prove this conjecture. This is a joint work with Suil O and Douglas B. West.
The Chv\'atal--Erd\H{o}s Theorem states that every graph whose connectivity is at least its independence number has a spanning cycle. In 1976, Fouquet and Jolivet conjectured an extension: If $G$ is an $n$-vertex $k$-connected graph with independence number $a$, and $a \ge k$, then $G$ has a cycle of length at least $\frac{k(n+a-k)}{a}$. We prove this conjecture. This is a joint work with Suil O and Douglas B. West.