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
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    generalized Turán problem
    0 references
    F-Turán good
    0 references
    flag algebra
    0 references
    \(P_3\)
    0 references
    0 references
    0 references
    0 references