Premium
Unavoidable cycle lengths in graphs
Author(s) -
Verstraete Jacques
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20072
Subject(s) - mathematics , combinatorics , conjecture , graph , degree (music) , constant (computer programming) , discrete mathematics , computer science , physics , acoustics , programming language
An old conjecture of Erdős states that there exists an absolute constant c and a set S of density zero such that every graph of average degree at least c contains a cycle of length in S . In this paper, we prove this conjecture by showing that every graph of average degree at least ten contains a cycle of length in a prescribed set S satisfying $|S \cap \{ 1,2,\ldots ,n\} | = O(n^{0.99})$ . © 2005 Wiley Periodicals, Inc. J Graph Theory