On Decomposition of Graphs into Nonisomorphic Independent Sets

Abstract

A decomposition into non-isomorphic matchings, or $DINIM$ for short, is a partition of the edges of a graph $G$ into matchings of different sizes. As a special case of our results, we prove that if a graph $G$ has at least $(2{\chi }^{\prime }–2){\chi }^{\prime }+1$ edges, where ${\chi }^{\prime }={\chi }^{\prime }(G)$ is the chromatic index of $G$, then $G$ has a $DINIM$. In particular, the $n$-dimensional cube, $Q_n$, $n\ge 4$, has a $DINIM$. These results confirm two conjectures which appeared in Chinn and Richter [3].