l+1-free and bipartite by l-partite. In our second main result we examine the class of epsilon-regular graphs in the context of the famous Regularity Lemma by Szemerédi. Whereas the case of dense graphs is well understood, the application of the Regularity Lemma for sparse random graphs still lacks an important keystone. This led to a conjecture by Kohayakawa, Luczak and Rödl, which is considered one of the most important open problems in the theory of random graphs. The conjecture states that complete subgraphs Kl occur with extremely high probability in sufficiently dense epsilon-regular graphs. We prove their conjecture for the subgraphs K4 and K5."/>