On star-forest ascending subgraph decomposition

Original · EN

The Ascending Subgraph Decomposition (ASD) Conjecture asserts that every graph G with n+1 2 edges admits an edge decomposition G=H₁⊕ ⊕ Hₙ such that Hᵢ has i edges and it is isomorphic to a subgraph of Hᵢ₊₁, i=1,,n-1. We show that every bipartite graph G with n+1 2 edges such that the degree sequence d₁,,dₖ of one of the stable sets satisfies dₖ₋ᵢ≥ n-i for each 0≤ i≤ 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.