Paths of length three are \(K_{r+1}\)-Turán-good (Q2121716)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Paths of length three are \(K_{r+1}\)-Turán-good |
scientific article |
Statements
Paths of length three are \(K_{r+1}\)-Turán-good (English)
0 references
4 April 2022
0 references
The generalized Turán problem ex(\(n, T, F\)) is to determine the maximal number of copies of a graph \( T\) that can exist in an \(F\)-free graph on \(n\) vertices. \textit{D. Gerbner} and \textit{C. Palmer} [``Some exact results for generalized Turán problems'', Preprint, \url{arXiv:2006.03756}] gave the name ``\(F\)-Turán-good'' to graphs \(T\) for which, for large enough \(n\), the solution to the generalized Turán problem is realized by a Turán graph. They prove that the path graph on two edges, \(P_2\), is \(K_{r+1}\)-Turán-good for all \(r \geq 3\), but they conjecture that the same result should hold for all \(P_{\ell}\). In this paper, using arguments based in flag algebras, the authors prove that the path on three edges, \(P_3\), is also \(K_{r+1}\)-Turán-good for all \(r \geq 3\).
0 references
generalized Turán problem
0 references
F-Turán good
0 references
flag algebra
0 references
\(P_3\)
0 references