On star forest ascending subgraph decomposition (Q510324): Difference between revisions

Summary: The ascending subgraph decomposition (ASD) conjecture asserts that every graph \(G\) with \({n+1\choose 2}\) 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,\ldots,n-1\). We show that every bipartite graph \(G\) with \({n+1\choose 2}\) edges such that the degree sequence \(d_1,\ldots,d_k\) of one of the stable sets satisfies \( d_{k-i}\geq n-i\; \text{for each}\; 0\leq i\leq 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.