Chen–Yang–Yuan–Zhang conjecture on cliques in graphs avoiding disjoint copies of P3P_3

Let nn, kk, and ss be integers, and let P3P_3 denote the path on three vertices. Write kP3kP_3 for the disjoint union of kk copies of P3P_3, and let MnM_n be the graph consisting of n/2\lfloor n/2\rfloor independent edges and at most one isolated vertex. Define

f(n,k,s)=(k1s)+(nk+1)(k1s1)+nk+12(k1s2).f(n,k,s)=\binom{k-1}{s}+(n-k+1)\binom{k-1}{s-1}+\left\lfloor\frac{n-k+1}{2}\right\rfloor\binom{k-1}{s-2}.

For a graph GG, 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 subgraph consisting of kk vertex-disjoint copies of P3P_3. Let In3k+1I_{n-3k+1} be an independent graph on n3k+1n-3k+1 vertices. Chen–Yang–Yuan–Zhang's conjecture. If n3kn\geq 3k and s3s\geq 3, then

ex(n,Ks,kP3)=max{(3k1s),f(n,k,s)}.\operatorname{ex}(n,K_s,kP_3)=\max\left\{\binom{3k-1}{s},f(n,k,s)\right\}.

Moreover, every extremal graph GG satisfies the following conditions: for 3sk+13\leq s\leq k+1, either GG is a subgraph of Kk1+Mnk+1K_{k-1}+M_{n-k+1}, or

K3k1In3k+1GK3k1Mn3k+1;K_{3k-1}\cup I_{n-3k+1}\subseteq G\subseteq K_{3k-1}\cup M_{n-3k+1};

for k+2s3k1k+2\leq s\leq 3k-1,

K3k1In3k+1GK3k1Mn3k+1.K_{3k-1}\cup I_{n-3k+1}\subseteq G\subseteq K_{3k-1}\cup M_{n-3k+1}.

Here ++ denotes disjoint union with all edges between the summands, and In3k+1I_{n-3k+1} has no edges. The conjecture gives an exact extremal formula together with a classification of all extremal graphs; its status is not resolved in the supplied source context.

Sources & referencesView supporting material

Primary source

Zhipeng Gao, Ping Li, Changhong Lu, Rui Sun and Long-Tu Yuan, “The maximum number of cliques in disjoint copies of graphs”, arXiv:2503.07072 (2025).

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.