On the ascending subgraph decomposition problem for bipartite graphs

Abstract

The Ascending Subgraph Decomposition (ASD) Conjecture asserts that every graph G with

n+1 2

edges admits an edge decomposition G = H has i edges and is isomorphic to a subgraph of H i+1 1 ⊕· · · ⊕H , i = 1, . . . , n−1. We show that every bipartite graph G with of one of the stable sets satisfies d

n+1 2

edges such that the degree sequence d ≥ n − i + 2, 1 ≤ i < k, 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.