Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-22T12:24:36.606Z Has data issue: false hasContentIssue false

A Bound on the Number of Edges in Graphs Without an Even Cycle

Published online by Cambridge University Press:  07 April 2016

BORIS BUKH
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: [email protected])
ZILIN JIANG
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: [email protected])

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.

Type
Paper
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Benson, C. T. (1966) Minimal regular graphs of girths eight and twelve. Canad. J. Math. 18 10911094.Google Scholar
[2] Blagojević, P. V. M., Bukh, B. and Karasev, R. (2013) Turán numbers for Ks,t -free graphs: Topological obstructions and algebraic constructions. Israel J. Math. 197 199214. arXiv:1108.5254.CrossRefGoogle Scholar
[3] Bondy, J. A. and Simonovits, M. (1974) Cycles of even length in graphs. J. Combin. Theory Ser. B 16 97105.Google Scholar
[4] Brown, W. G. (1966) On graphs that do not contain a Thomsen graph. Canad. Math. Bull. 9 281285.Google Scholar
[5] Erdős, P. (1938) On sequences of integers no one of which divides the product of two others and on some related problems. Inst. Math. Mech. Univ. Tomsk 2 7482.Google Scholar
[6] Erdős, P. (1964) Extremal problems in graph theory. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Publ. House Czechoslovak Academy of Sciences, Prague, pp. 2936.Google Scholar
[7] Erdős, P. and Rényi, A. (1962) On a problem in the theory of graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 623641.Google Scholar
[8] Füredi, Z. and Simonovits, M. (2013) The history of degenerate (bipartite) extremal graph problems. Bolyai Soc. Math. Stud. 25 169264. arXiv:1306.5167.Google Scholar
[9] Füredi, Z., Naor, A. and Verstraëte, J. (2006) On the Turán number for the hexagon. Adv. Math. 203 476496.Google Scholar
[10] Keevash, P. (2011) Hypergraph Turán problems. In Surveys in Combinatorics 2011, Vol. 392 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 83139.Google Scholar
[11] Kővari, T., Sós, V. T. and Turán, P. (1954) On a problem of K. Zarankiewicz. Colloquium Math. 3 5057.Google Scholar
[12] Lazebnik, F. and Ustimenko, V. A. (1995) Explicit construction of graphs with an arbitrary large girth and of large size. Discrete Appl. Math. 60 275284.Google Scholar
[13] Mellinger, K. E. and Mubayi, D. (2005) Constructions of bipartite graphs from finite geometries. J. Graph Theory 49 110.Google Scholar
[14] Pikhurko, O. (2012) A note on the Turán function of even cycles. Proc. Amer. Math. Soc. 140 36873692.Google Scholar
[15] Sidorenko, A. (1995) What we know and what we do not know about Turán numbers. Graphs Combin. 11 179199.Google Scholar
[16] Simonovits, M. (1968) A method for solving extremal problems in graph theory, stability problems. In Theory of Graphs: Proc. Colloq. Tihany 1966, Academic, pp. 279319.Google Scholar
[17] Turán, P. (1941) On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok 48 436452.Google Scholar
[18] Verstraëte, J. (2000) On arithmetic progressions of cycle lengths in graphs. Combin. Probab. Comput. 9 369373. arXiv:math/0204222.CrossRefGoogle Scholar
[19] Wenger, R. (1991) Extremal graphs with no C 4's, C 6's, or C 10's. J. Combin. Theory Ser. B 52 113116.Google Scholar