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

About 1 year old · traced to

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)=(k−1s)+(n−k+1)(k−1s−1)+⌊n−k+12⌋(k−1s−2).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 In−3k+1I_{n-3k+1} be an independent graph on n−3k+1n-3k+1 vertices. Chen–Yang–Yuan–Zhang's conjecture. If n≥3kn\geq 3k and s≥3s\geq 3, then

ex⁡(n,Ks,kP3)=max⁡{(3k−1s),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 3≤s≤k+13\leq s\leq k+1, either GG is a subgraph of Kk−1+Mn−k+1K_{k-1}+M_{n-k+1}, or

K3k−1∪In−3k+1⊆G⊆K3k−1∪Mn−3k+1;K_{3k-1}\cup I_{n-3k+1}\subseteq G\subseteq K_{3k-1}\cup M_{n-3k+1};

for k+2≤s≤3k−1k+2\leq s\leq 3k-1,

K3k−1∪In−3k+1⊆G⊆K3k−1∪Mn−3k+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 In−3k+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.

References

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.