Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2509.18567 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908554802233344 |
|---|---|
| author | Nie, Jiaxi Ren, Yibo Wu, Hehui |
| author_facet | Nie, Jiaxi Ren, Yibo Wu, Hehui |
| contents | A $k$-star-forest is a forest with at most $k$ connected components where each component is a star. Let $F_k(n)$ be the minimum integer such that the complete graph on $n$ vertices can be decomposed into $F_k(n)$ $k$-star-forests. Pach, Saghafian and Schnider showed that $F_2(n)=\lceil 3n/4 \rceil$. In this paper, we show that $F_3(n)=5n/9$ when $n$ is a multiple of 27. Further, for $k\ge 4$, we show that $F_k(n)=n/2+2$ when $n>2k$ and $n\equiv 4 \pmod{12}$. Our results disprove a conjecture of Pach, Saghafian and Schnider. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_18567 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Decomposition of Cliques into $k$-Star-Forests Nie, Jiaxi Ren, Yibo Wu, Hehui Combinatorics 05B40, 05C35, 05C70 A $k$-star-forest is a forest with at most $k$ connected components where each component is a star. Let $F_k(n)$ be the minimum integer such that the complete graph on $n$ vertices can be decomposed into $F_k(n)$ $k$-star-forests. Pach, Saghafian and Schnider showed that $F_2(n)=\lceil 3n/4 \rceil$. In this paper, we show that $F_3(n)=5n/9$ when $n$ is a multiple of 27. Further, for $k\ge 4$, we show that $F_k(n)=n/2+2$ when $n>2k$ and $n\equiv 4 \pmod{12}$. Our results disprove a conjecture of Pach, Saghafian and Schnider. |
| title | Decomposition of Cliques into $k$-Star-Forests |
| topic | Combinatorics 05B40, 05C35, 05C70 |
| url | https://arxiv.org/abs/2509.18567 |