Transversal designs and induced decompositions of graphs

Csilla Bujtás, Zsolt Tuza

We prove that for every complete multipartite graph $F$ there exist very dense graphs $G_n$ on $n$ vertices, namely with as many as $\left(\genfrac{}{}{0ex}{}{n}{2}\right)-cn$ edges for all $n$, for some co…