Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-02-06T20:08:46.158Z Has data issue: false hasContentIssue false
  • English
  • Français

Turán Number of an Induced Complete Bipartite Graph Plus an Odd Cycle

Part of: Graph theory

Published online by Cambridge University Press:  16 July 2018

BEKA ERGEMLIDZE ,
ERVIN GYŐRI  and
ABHISHEK METHUKU
BEKA ERGEMLIDZE
Affiliation:
Department of Mathematics, Central European University, 1051 Budapest, Nádor utca 9 (e-mail: beka.ergemlidze@gmail.com, abhishekmethuku@gmail.com)
ERVIN GYŐRI
Affiliation:
MTA Rényi Institute, 1053 Budapest, Reáltanoda utca 13-15 and Department of Mathematics, Central European University, 1051 Budapest, Nádor utca 9 (e-mail: gyori.ervin@renyi.mta.hu)
ABHISHEK METHUKU
Affiliation:
Department of Mathematics, Central European University, 1051 Budapest, Nádor utca 9 (e-mail: beka.ergemlidze@gmail.com, abhishekmethuku@gmail.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let k ⩾ 2 be an integer. We show that if s = 2 and t ⩾ 2, or s = t = 3, then the maximum possible number of edges in a C2k+1-free graph containing no induced copy of Ks,t is asymptotically equal to (t − s + 1)1/s(n/2)2−1/s except when k = s = t = 2.

This strengthens a result of Allen, Keevash, Sudakov and Verstraëte [1], and answers a question of Loh, Tait, Timmons and Zhou [14].

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05C69: Dominating sets, independent sets, cliques
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 2 , March 2019 , pp. 241 - 252
Copyright
Copyright © Cambridge University Press 2018 

References

[1] Allen, P., Keevash, P., Sudakov, B. and Verstraëte, J. (2014) Turán numbers of bipartite graphs plus an odd cycle. J. Combin. Theory Ser. B 106 134–162.Google Scholar
[2] Alon, N., Rónyai, L. and Szabó, T. (1999) Norm-graphs: Variations and applications. J. Combin. Theory Ser. B 76 280–290.Google Scholar
[3] Blakley, R. G. and Roy, P. (1965) A Hölder type inequality for symmetric matrices with nonnegative entries. Proc. Amer. Math. Soc. 16 1244–1245.Google Scholar
[4] Bollobás, B. and Győri, E. (2008) Pentagons vs. triangles. Discrete Math. 308 4332–4336.Google Scholar
[5] Brown, W. G. (1966) On graphs that do not contain a Thomsen graph. Canad. Math. Bull. 9 281–285.Google Scholar
[6] Erdős, P. and Gallai, T. (1959) On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar. 10 337–356.Google Scholar
[7] Erdős, P. and Simonovits, M. (1982) Compactness results in extremal graph theory. Combinatorica 2 275–288.Google Scholar
[8] Erdős, P., Rényi, A. and Sós, V. T. (1966) On a problem of graph theory. Stud Sci. Math. Hungar. 1 215–235.Google Scholar
[9] Füredi, Z. (1996) An upper bound on Zarankiewicz' problem. Combin. Probab. Comput. 5 29–33.Google Scholar
[10] Füredi, Z. (1996) New asymptotics for bipartite Turán numbers. J. Combin. Theory Ser. A 75 141–144.Google Scholar
[11] Győri, E. and Li, H. (2012) The maximum number of triangles in C 2k+1-free graphs. Combin. Probab. Comput. 21 187–191.Google Scholar
[12] Kollár, J., Rónyai, L. and Szabó, T. (1996) Norm-graphs and bipartite Turán numbers. Combinatorica 16 399–406.Google Scholar
[13] Kővári, T., Sós, V. and Turán, P. (1954) On a problem of K. Zarankiewicz. Colloquium Math. 3 50–57.Google Scholar
[14] Loh, P., Tait, M., Timmons, C. and Zhou, R. M. (2017) Induced Turán numbers. Combin. Probab. Comput. 27 274–288.Google Scholar