Some exact results for generalized Turán problems

Dániel Gerbner, Cory Palmer

Research output: Contribution to journalArticlepeer-review

11 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 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.

Original languageEnglish
Article number103519
JournalEuropean Journal of Combinatorics
Volume103
DOIs
StatePublished - Jun 2022

Fingerprint

Dive into the research topics of 'Some exact results for generalized Turán problems'. Together they form a unique fingerprint.

Cite this