Pach–Saghafian–Schnider conjecture on decompositions of cliques into k-star-forests
Pach–Saghafian–Schnider conjecture on decompositions of cliques into k-star-forests
A -star-forest is a star-forest with at most connected components. Let be the minimum integer such that the complete graph on vertices can be decomposed into -star-forests.
Pach–Saghafian–Schnider conjecture. For any ,
This lower bound asserts that the construction obtained from the broken double-star decomposition together with matchings of size at most is best possible for decomposing cliques into -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.