← All problems

Turán problem for three disjoint cliques

For integers p≥q≥r≥2p\ge q\ge r\ge 2 and n≥p+q+rn\ge p+q+r, determine the maximum number of edges in an nn-vertex graph containing no subgraph isomorphic to Kp∪Kq∪KrK_p\cup K_q\cup K_r, namely determine ex⁡(n,Kp∪Kq∪Kr)\operatorname{ex}(n,K_p\cup K_q\cup K_r), and characterize all nn-vertex graphs attaining this maximum.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

An unrefereed paper claims to determine the exact answer for forbidding any three disjoint cliques, while cases involving four or more cliques remain open.

The problem asks for the maximum number of edges in an nn-vertex graph containing no three disjoint cliques KpK_p, KqK_q, and KrK_r, together with all extremal graphs.

October 2026 exact-value claim

Alexandr Kostochka, Dadong Peng, Zimu Xiang, and Liang Zhang claim exact values and all extremal graphs for p≥q≥r≥2p \ge q \ge r \ge 2 and n≥p+q+rn \ge p+q+r. This would settle the full three-clique problem, but the preprint is unrefereed. The corresponding problem for four or more disjoint cliques remains outside scope.

Current status (as of October 2026): The three-clique case is claimed solved for all p≥q≥r≥2p \ge q \ge r \ge 2 and n≥p+q+rn \ge p+q+r, subject to verification; cases with four or more disjoint cliques remain open.

Sources

Solutions 0

No solutions have been posted yet.