2025/09/23 by Nie, Jiaxi, Hehui Wu, Ren, Yibo +1
Computer Science · #05B40 #05C35 #05C70 #Advanced Database Systems and Queries #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2509.18567
openalex publication_date 2025/09/23 · openalex created_date 2025/10/16 · openalex updated_date 2026/07/28
A k-star-forest is a forest with at most k connected components where each component is a star. Let Fk(n) be the minimum integer such that the complete graph on n vertices can be decomposed into Fk(n) k-star-forests. Pach, Saghafian and Schnider showed that F2(n)=\lceil 3n/4 \rceil. In this paper, we show that F3(n)=5n/9 when n is a multiple of 27. Further, for k≥ 4, we show that Fk(n)=n/2+2 when n>2k and n≡ 4 \pmod12. Our results disprove a conjecture of Pach, Saghafian and Schnider.