Some exact results for generalized Turán problems

DOI10.1016/J.EJC.2022.103519zbMATH Open1494.05058arXiv2006.03756OpenAlexW4213458687MaRDI QIDQ2136200FDOQ2136200

Dániel Gerbner, Cory Palmer

Publication date: 10 May 2022

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

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.

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)

Cites Work

• On the number of pentagons in triangle-free graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the structure of linear graphs
• On the maximum number of five-cycles in a triangle-free graph
• Extremal graphs for intersecting triangles
• A Spectral Erdős–Stone–Bollobás Theorem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Pentagons vs. triangles
• The inducibility of graphs
• On the number of \(C_ 5's\) in a triangle-free graph
• The maximum number of triangles in \(C_{2k+1}\)-free graphs
• Many \(T\) copies in \(H\)-free graphs
• Supersaturation for subgraph counts
• On the maximal number of certain subgraphs in \(K_ r\)-free graphs
• A note on the maximum number of triangles in a C₅‐free graph
• Generalized Turán problems for disjoint copies of graphs
• Generalized Turán problems for even cycles
• Some sharp results on the generalized Turán numbers
• A Generalized Turán Problem and its Applications
• Counting copies of a fixed subgraph in \(F\)-free graphs
• The maximum number of $P_\ell$ copies in $P_k$-free graphs

Cited In (20)

• Title not available (Why is that?)
• Some sharp results on the generalized Turán numbers
• Some exact results of the generalized Turán numbers for paths
• On triangle-free graphs maximizing embeddings of bipartite graphs
• Generalized Turán problems for double stars
• Paths are Turán-good
• Every graph is eventually Turán-good
• On the Fon-Der-Flaass interpretation of extremal examples for Turán's \((3,4)\)-problem
• A localized approach to generalized Turán problems
• On supersaturation and stability for generalized Turán problems
• Generalized Turán problems for \(K_{2,t}\)
• On extremal values of some degree-based topological indices with a forbidden or a prescribed subgraph
• The cycle of length four is strictly \(F\)-Turán-good
• Generalized regular Turán numbers
• Stability from graph symmetrization arguments in generalized Turán problems
• Generalized Turán densities in the hypercube
• On generalized Turán numbers of intersecting cliques
• Some exact results for non-degenerate generalized Turán problems
• Triangles in graphs without bipartite suspensions
• On non-degenerate Berge-Turán problems

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)