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

Less than 1 year old · traced to

For integers nn, kk, and ss, let H(n,k,q)H(n,k,q) be the graph construction defined above, and for s≥2s\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 n≥3kn\geq 3k and s≥3s\geq 3,

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

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

G⊆H(n,k,k−1),G\subseteq H(n,k,k-1),

or

K3k−1∪In−3k+1⊆G⊆H(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 3≤s≤3k−13\leq s\leq 3k-1.

References

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.