×

On the problem of ascending subgraph decompositions into matchings. (English) Zbl 0832.05085

A graph \(G\) with \(q\) edges where \({n+ 1\choose 2}\leq q<{n+ 2\choose 2}\) is said to have an ascending subgraph decomposition (ASD) if \(G\) can be decomposed into \(n\) subgraphs \(G_1, G_2,\dots, G_n\) without isolated vertices such that \(G_i\) is isomorphic to a proper subgraph of \(G_{i+ 1}\) for \(1\leq i\leq n- 1\). The author shows that if \(G\) is a graph with \(\left(\begin{smallmatrix} n+ 1\\ 2\end{smallmatrix}\right)\) edges and edge chromatic number at most \((n+ 2)/2\), then \(G\) has an ASD \(G_1, G_2,\dots, G_n\) such that \(G_i\) is isomorphic to \(iK_2\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)