Nearly complete graphs decomposable into large induced matchings and their applications
Nearly complete graphs decomposable into large induced matchings and their applications
We describe two constructions of (very) dense graphs which are edge disjoint unions of large induced matchings. The first construction exhibits graphs on N vertices with {N \choose 2}-o(N^2) edges, which can be decomposed into pairwise disjoint induced matchings, each of size N^{1-o(1)} . The second construction provides a covering …