Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656996 | Journal of Combinatorial Theory, Series B | 2011 | 6 Pages |
Abstract
The Chvátal–Erdő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⩾k, then G has a cycle with length at least . We prove this conjecture.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics