Discrete Mathematics and Optimization Seminar
Mar. 14th, 2011
Hehui Wu
Longest Cycles in Graphs with Given Independence Number and Connectivity
University of Illinois at Urbana-Champaign
Abstract: The Chvatal--Erdos 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 >= k, then G has a cycle of length at least k(n+a-k)/a. We prove this conjecture. This is a joint work with Suil O and Douglas B. West.