On the ascending subgraph decompositions of regular graphs
Let \(G\) be a graph with \(q\) edges and let \(n\) be a positive integer such that \(\binom{n+1}2\leq q<\binom{n+2}2\). Then \(G\) has an ascending subgraph decomposition 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}\), \(1\leq i<n\). In the paper it is proved that if \(G\) is an \(r\)-regular graph with \(q=\binom{n+1}2\) edges such that \(r\leq\frac 23(n+\delta_{\Delta(G),\chi'(G)})\), then \(G\) has an ascending subgraph decomposition. (Here \(\delta\) is the Kronecker delta.) Moreover, it is proved that every regular bipartite graph has an ascending subgraph decomposition.
scientific article; zbMATH DE number 1193543