Some exact results for generalized Turán problems

Dániel Gerbner; Cory Palmer

doi:10.1016/j.ejc.2022.103519

Some exact results for generalized Turán problems

Dániel Gerbner, Cory Palmer

Mathematical Sciences

Hungarian Academy of Sciences

Research output: Contribution to journal › Article › peer-review

21 Scopus citations

Abstract

Fix a k-chromatic graph F. In this paper we consider the question to determine for which graphs H does the Turán graph T_k−1(n) have the maximum number of copies of H among all n-vertex F-free graphs (for n large enough). We say that such a graph H is F-Turán-good. In addition to some general results, we give (among others) the following concrete results: (i) For every complete multipartite graph H, there is k large enough such that H is K_k-Turán-good. (ii) The path P₃ is F-Turán-good for F with χ(F)≥4. (iii) The path P₄ and cycle C₄ are C₅-Turán-good. (iv) The cycle C₄ is F₂-Turán-good where F₂ is the graph of two triangles sharing exactly one vertex.

Original language	English
Article number	103519
Journal	European Journal of Combinatorics
Volume	103
DOIs	https://doi.org/10.1016/j.ejc.2022.103519
State	Published - Jun 2022

Funding

Research supported by the János Bolyai Research Fellowship of the Hungarian Academy of Sciences and the National Research, Development and Innovation Office – NKFIH, Hungary under the grants FK 132060, KKP-133819, KH130371 and SNN 129364.Research supported by a grant from the Simons Foundation #712036.

Funders	Funder number
Simons Foundation	712036
SNN 129364, KH130371, KKP-133819, FK 132060

Access to Document

10.1016/j.ejc.2022.103519

Cite this

@article{1465de451f034a21b4721be79761d35b,

title = "Some exact results for generalized Tur{\'a}n problems",

abstract = "Fix a k-chromatic graph F. In this paper we consider the question to determine for which graphs H does the Tur{\'a}n graph Tk−1(n) have the maximum number of copies of H among all n-vertex F-free graphs (for n large enough). We say that such a graph H is F-Tur{\'a}n-good. In addition to some general results, we give (among others) the following concrete results: (i) For every complete multipartite graph H, there is k large enough such that H is Kk-Tur{\'a}n-good. (ii) The path P3 is F-Tur{\'a}n-good for F with χ(F)≥4. (iii) The path P4 and cycle C4 are C5-Tur{\'a}n-good. (iv) The cycle C4 is F2-Tur{\'a}n-good where F2 is the graph of two triangles sharing exactly one vertex.",

author = "D{\'a}niel Gerbner and Cory Palmer",

note = "Publisher Copyright: {\textcopyright} 2022 Elsevier Ltd",

year = "2022",

month = jun,

doi = "10.1016/j.ejc.2022.103519",

language = "English",

volume = "103",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

TY - JOUR

T1 - Some exact results for generalized Turán problems

AU - Gerbner, Dániel

AU - Palmer, Cory

PY - 2022/6

Y1 - 2022/6

N2 - Fix a k-chromatic graph F. In this paper we consider the question to determine for which graphs H does the Turán graph Tk−1(n) have the maximum number of copies of H among all n-vertex F-free graphs (for n large enough). We say that such a graph H is F-Turán-good. In addition to some general results, we give (among others) the following concrete results: (i) For every complete multipartite graph H, there is k large enough such that H is Kk-Turán-good. (ii) The path P3 is F-Turán-good for F with χ(F)≥4. (iii) The path P4 and cycle C4 are C5-Turán-good. (iv) The cycle C4 is F2-Turán-good where F2 is the graph of two triangles sharing exactly one vertex.

AB - Fix a k-chromatic graph F. In this paper we consider the question to determine for which graphs H does the Turán graph Tk−1(n) have the maximum number of copies of H among all n-vertex F-free graphs (for n large enough). We say that such a graph H is F-Turán-good. In addition to some general results, we give (among others) the following concrete results: (i) For every complete multipartite graph H, there is k large enough such that H is Kk-Turán-good. (ii) The path P3 is F-Turán-good for F with χ(F)≥4. (iii) The path P4 and cycle C4 are C5-Turán-good. (iv) The cycle C4 is F2-Turán-good where F2 is the graph of two triangles sharing exactly one vertex.

UR - https://www.scopus.com/pages/publications/85125116220

U2 - 10.1016/j.ejc.2022.103519

DO - 10.1016/j.ejc.2022.103519

M3 - Article

AN - SCOPUS:85125116220

SN - 0195-6698

VL - 103

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103519

ER -

Some exact results for generalized Turán problems

Abstract

Funding

Access to Document

Other files and links

Fingerprint

Cite this