Han–Zhao conjecture on vertex-disjoint cliques in multipartite graphs

About 4 years old · traced to

Let r≥t≥3r\geq t\geq 3 and k≥2k\geq 2, and let KtK_{t} denote the complete graph on tt vertices. For positive integers n1,…,nrn_1,\ldots,n_r, write Kn1,…,nrK_{n_1,\ldots,n_r} for the complete rr-partite graph with part sizes n1,…,nrn_1,\ldots,n_r, and let ex⁡(n1,…,nr,kKt)\operatorname{ex}(n_1,\ldots,n_r,kK_t) be the maximum number of edges in an rr-partite graph with these part sizes that contains no vertex-disjoint union of kk copies of KtK_t. Let f(n1,…,nr,k,t)f(n_1,\ldots,n_r,k,t) be the function specified in the cited formulation. Assume that nrn_r is sufficiently large. Han–Zhao's conjecture.

ex⁡(n1,…,nr,kKt)=f(n1,…,nr,k,t).\operatorname{ex}(n_1,\ldots,n_r,kK_t)=f(n_1,\ldots,n_r,k,t).

This conjecture concerns the extremal number for forbidding kk vertex-disjoint copies of a clique in a multipartite graph. It extends the problem posed after earlier results for kK2kK_2 and for general multipartite graphs, while the source does not state a resolution of the general case.

References

Primary source

Wanfang Chen, Changhong Lu and Long-Tu Yuan, “A stability theorem for multi-partite graphs”, arXiv:2208.13995 (2022).

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.