Back to Search Start Over

A bound on the number of edges in graphs without an even cycle

Authors :
Boris Bukh
Zilin Jiang
Publication Year :
2014
Publisher :
arXiv, 2014.

Abstract

We show that, for each fixed $k$, an $n$-vertex graph not containing a cycle of length $2k$ has at most $80\sqrt{k}\log k\cdot n^{1+1/k}+O(n)$ edges.<br />Comment: 16 pages, v2 appeared in Comb. Probab. Comp., v3 fixes an error in v2 and explains why the method in the paper cannot improve the power of k further, v4 fixes the proof of Theorem 12 introduced in v3

Details

Database :
OpenAIRE
Accession number :
edsair.doi.dedup.....7d300841c33373e862c7d030483d50b0
Full Text :
https://doi.org/10.48550/arxiv.1403.1601