Chen–Yang–Yuan–Zhang conjecture for generalized Turán numbers of linear paths

For integers nn, kk, and ss, let H(n,k,q)H(n,k,q) be the graph construction defined above, and for s2s\geq 2 write

hs(n,k,q):=N(Ks,H(n,k,q)).h_s(n,k,q):=N\bigl(K_s,H(n,k,q)\bigr).

Let ex(n,Ks,kP3)\operatorname{ex}(n,K_s,kP_3) denote the maximum number of copies of KsK_s in an nn-vertex graph containing no kk vertex-disjoint copies of the path P3P_3.

Chen–Yang–Yuan–Zhang conjecture. For n3kn\geq 3k and s3s\geq 3,

ex(n,Ks,kP3)=max{hs(n,k,0),hs(n,k,k1)}.\operatorname{ex}(n,K_s,kP_3)=\max\{h_s(n,k,0),h_s(n,k,k-1)\}.

Moreover, if 3s3k13\leq s\leq 3k-1, then every extremal graph GG satisfies either

GH(n,k,k1),G\subseteq H(n,k,k-1),

or

K3k1In3k+1GH(n,k,0).K_{3k-1}\cup I_{n-3k+1}\subseteq G\subseteq H(n,k,0).

This generalizes the known exact edge-counting result for P3P_3-packings to clique counts. The conjecture compares the two constructions that are extremal when s=2s=2; the asserted characterization further restricts all extremal graphs for 3s3k13\leq s\leq 3k-1.

Sources & referencesView supporting material

Primary source

Qi Wu and Long-Tu Yuan, “Exact generalized Turán number of vertex-disjoint paths of length two”, arXiv:2607.18122 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.