A Note on Graphs Without Short Even Cycles

  • Thomas Lam
  • Jacques Verstraëte

Abstract

In this note, we show that any $n$-vertex graph without even cycles of length at most $2k$ has at most ${1\over2}n^{1 + 1/k} + O(n)$ edges, and polarity graphs of generalized polygons show that this is asymptotically tight when $k \in \{2,3,5\}$.

Published
2005-04-06
Article Number
N5