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}\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.
@article{10_37236_5380,
author = {Josep M. Aroca and Anna Llad\'o},
title = {On star forest ascending subgraph decomposition},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {1},
doi = {10.37236/5380},
zbl = {1355.05191},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5380/}
}
TY - JOUR
AU - Josep M. Aroca
AU - Anna Lladó
TI - On star forest ascending subgraph decomposition
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/5380/
DO - 10.37236/5380
ID - 10_37236_5380
ER -
%0 Journal Article
%A Josep M. Aroca
%A Anna Lladó
%T On star forest ascending subgraph decomposition
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/5380/
%R 10.37236/5380
%F 10_37236_5380
Josep M. Aroca; Anna Lladó. On star forest ascending subgraph decomposition. The electronic journal of combinatorics, Tome 24 (2017) no. 1. doi: 10.37236/5380
