Some exact results for generalized Turán problems

DOI10.1016/J.EJC.2022.103519MaRDI QIDQ2136200zbMATH OpenOpenAlexFDO

Authors Dániel Gerbner, Cory Palmer

Publication date 10 May 2022

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.03756

zbMATH Keywords

cyclepathcolor-criticalforbidden subgraph problemTurán graphTurán-good

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Abstract: Fix a $k$-chromatic graph $F$. In this paper we consider the question to determine for which graphs $H$ does the Tur'an 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'an-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'an-good. (ii) The path $P_3$ is $F$-Tur'an-good for $F$ with $chi(F)geq4$. (iii) The path $P_4$ and cycle $C_4$ are $C_5$-Tur'an-good. (iv) The cycle $C_4$ is $F_2$-Tur'an-good where $F_2$ is the graph of two triangles sharing exactly one vertex.

Recommendations

• On Turán-good graphs
• Some exact results of the generalized Turán numbers for paths
• Some results on \(k\)-Turán-good graphs
• Paths of length three are \(K_{r+1}\)-Turán-good
• Some sharp results on the generalized Turán numbers

Cites work

• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• A generalized Turán problem and its applications
• A note on the maximum number of triangles in a C₅‐free graph
• A spectral Erdős-Stone-Bollobás theorem
• Counting copies of a fixed subgraph in \(F\)-free graphs
• Extremal graphs for intersecting triangles
• Generalized Turán problems for disjoint copies of graphs
• Generalized Turán problems for even cycles
• Many \(T\) copies in \(H\)-free graphs
• On the maximal number of certain subgraphs in \(K_ r\)-free graphs
• On the maximum number of five-cycles in a triangle-free graph
• On the number of \(C_ 5's\) in a triangle-free graph
• On the number of pentagons in triangle-free graphs
• On the structure of linear graphs
• Pentagons vs. triangles
• Some sharp results on the generalized Turán numbers
• Supersaturation for subgraph counts
• The inducibility of graphs
• The maximum number of $P_\ell$ copies in $P_k$-free graphs
• The maximum number of triangles in \(C_{2k+1}\)-free graphs

Cited in

(28)

• Paths of length three are \(K_{r+1}\)-Turán-good
• Additive approximation of generalized Turán questions
• Extremal graphs for the \(k\)-flower
• Generalized Turán problems for double stars
• Paths are Turán-good
• Stability from graph symmetrization arguments in generalized Turán problems
• The cycle of length four is strictly \(F\)-Turán-good
• Some exact results for non-degenerate generalized Turán problems
• Generalized Turán densities in the hypercube
• Generalized regular Turán numbers
• A localized approach to generalized Turán problems
• Generalized Turán problems for \(K_{2,t}\)
• LARGE -FREE SUBGRAPHS IN -CHROMATIC GRAPHS
• On extremal values of some degree-based topological indices with a forbidden or a prescribed subgraph
• On multicolor Turán numbers
• Triangles in graphs without bipartite suspensions
• On the Fon-Der-Flaass interpretation of extremal examples for Turán's \((3,4)\)-problem
• On supersaturation and stability for generalized Turán problems
• Every graph is eventually Turán-good
• On non-degenerate Berge-Turán problems
• Some sharp results on the generalized Turán numbers
• Generalized planar Turán numbers
• Some exact results of the generalized Turán numbers for paths
• On triangle-free graphs maximizing embeddings of bipartite graphs
• On generalized Turán numbers of intersecting cliques
• On Turán-good graphs
• scientific article; zbMATH DE number 3827993 (Why is no real title available?)
• Some results on \(k\)-Turán-good graphs

This page was built for publication: Some exact results for generalized Turán problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136200)