Some exact results for generalized Turán problems

2020/06/06 by Gerbner, Dániel, Palmer, Cory
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2006.03756

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.

Related

• Some Results on k-Turán-good Graphs
• Some exact results of the generalized Turán numbers for paths
• On Turán-good graphs
• The cycle of length four is strictly F-Turán-good
• Paths are Turán-good