Ascending Subgraph Decomposition

Abstract

A typical theme for many well-known decomposition problems is to show that some obvious necessary conditions for decomposing a graph $G$ into copies $H_1,\dots ,H_m$ are also sufficient. One such problem was posed in 1987, by Alavi, Boals, Chartrand, Erdős, and Oellerman. They conjectured that the edges of every graph with $\left(\genfrac{}{}{0ex}{}{m+1}{2}\right)$ edges can be decomposed into subgraphs $H_1,\dots ,H_m$ such that each $H_i$ has $i$ edges and is isomorphic to a subgraph of $H_{i+1}$. In this paper we prove this conjecture for sufficiently large $m$.