Article ID Journal Published Year Pages File Type
4656996 Journal of Combinatorial Theory, Series B 2011 6 Pages PDF
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