## Abstract

A long-standing conjecture of Erdo{combining double acute accent}s and Simonovits is that ex ( n, C_{2 k} ), the maximum number of edges in an n-vertex graph without a 2 k-gon is asymptotically frac(1, 2) n^{1 + 1 / k} as n tends to infinity. This was known almost 40 years ago in the case of quadrilaterals. In this paper, we construct a counterexample to the conjecture in the case of hexagons. For infinitely many n, we prove that{A formula is presented}We also show that ex ( n, C_{6} ) {less-than or slanted equal to} λ n^{4 / 3} + O ( n ) < 0.6272 n^{4 / 3} if n is sufficiently large, where λ is the real root of 16 λ^{3} - 4 λ^{2} + λ - 3 = 0. This yields the best-known upper bound for the number of edges in a hexagon-free graph. The same methods are applied to find a tight bound for the maximum size of a hexagon-free 2 n × n bipartite graph.

Original language | English (US) |
---|---|

Pages (from-to) | 476-496 |

Number of pages | 21 |

Journal | Advances in Mathematics |

Volume | 203 |

Issue number | 2 |

DOIs | |

State | Published - Jul 10 2006 |

## Keywords

- Excluded cycles
- Extremal graph theory
- Turán numbers

## ASJC Scopus subject areas

- General Mathematics