Pach–Saghafian–Schnider conjecture on decompositions of cliques into k-star-forests

A kk-star-forest is a star-forest with at most kk connected components. Let Fk(n)F_k(n) be the minimum integer such that the complete graph on nn vertices can be decomposed into Fk(n)F_k(n) kk-star-forests.

Pach–Saghafian–Schnider conjecture. For any nk2n\ge k\ge 2,

Fk(n)(k+1)n2k.F_k(n)\ge \left\lceil\frac{(k+1)n}{2k}\right\rceil.

This lower bound asserts that the construction obtained from the broken double-star decomposition together with matchings of size at most kk is best possible for decomposing cliques into kk-star-forests. The statement is presented as a conjecture in the source; no resolution is given here.

Sources & referencesView supporting material

Primary source

Jiaxi Nie, Yibo Ren and Hehui Wu, “Decomposition of Cliques into k-Star-Forests”, arXiv:2509.18567 (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.