Proceedings of the American Mathematical Society · 2012 · 53 citations · 17 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationComputational ComplexityEnumerative CombinatoricsGraph AlgorithmsGraph TheoryOpen QuestionsUpper Bound ComputationUpper Bound Theorem
The Turán function $\mathrm {ex}(n,F)$ is the maximum number of edges in an $F$-free graph on $n$ vertices. The question of estimating this function for $F=C_{2k}$, the cycle of length $2k$, is one of the central open questions in this area that goes back to the 1930s. We prove that \[ \mathrm {ex}(n,C_{2k})\le (k-1) n^{1+1/k}+16(k-1)n, \] improving the previously best known general upper bound of Verstraëte [Combin. Probab. Computing 9 (2000), 369â373] by a factor $8+o(1)$ when $n\gg k$.
17
Cycles of even length in graphs
J. A. Bondy, Miklós Simonovits · Journal of Combinatorial Theory Series B · 1974 · 412 citations
On Graphs that do not Contain a Thomsen Graph
William G. Brown · Canadian Mathematical Bulletin · 1966 · 390 citations · Full text
Extremal problems in graph theory
Christopher M. Hartman · 1997 · 238 citations