COLLOQUIUM
DEPARTMENT OF MATHEMATICS AND STATISTICS
OAKLAND UNIVERSITY
ROCHESTER, MICHIGAN 48309
Suil O
University of Illinois
Longest Cycles in
$k$-connected Graphs with Given Independence Number
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 with length at least ${k(n+a-k)}/{a}$.
We prove this conjecture.
Monday, February 7, 2011
3:30 – 4:30 P.M.
372 Science and Engineering Building
(Refreshments at 3:00-3:30 PM in the kitchen area adjacent to 368 SEB)