On star-forest ascending subgraph decomposition

Abstract

The Ascending Subgraph Decomposition (ASD) Conjecture asserts that every graph $G$ with $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)$ edges admits an edge decomposition $G=H_1\oplus \cdots \oplus H_n$ such that $H_i$ has $i$ edges and it is isomorphic to a subgraph of $H_{i+1}$, $i=1,\dots ,n-1$. We show that every bipartite graph $G$ with $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)$ edges such that the degree sequence $d_1,\dots ,d_k$ of one of the stable sets satisfies $d_{k-i}\ge n-i\text{for each}0\le i\le k-1,$, admits an ascending subgraph decomposition with star forests. We also give a necessary condition on the degree sequence which is not far from the above sufficient one.

11 pages