Properly coloured copies and rainbow copies of large graphs with small maximum degree

Let G be a graph on n vertices with maximum degree Δ. We use the Lovász local lemma to show the following two results about colourings χ of the edges of the complete graph K n . If for each vertex v of K n the colouring χ assigns each colour to at most ( n ‐ 2)/(22.4Δ 2 ) edges emanating from v , then there is a copy of G in K n which is properly edge‐coloured by χ. This improves on a result of Alon, Jiang, Miller, and Pritikin [Random Struct. Algorithms 23(4), 409–433, 2003]. On the other hand, if χ assigns each colour to at most n /(51Δ 2 ) edges of K n , then there is a copy of G in K n such that each edge of G receives a different colour from χ. This proves a conjecture of Frieze and Krivelevich [Electron. J. Comb. 15(1), R59, 2008]. Our proofs rely on a framework developed by Lu and Székely [Electron. J. Comb. 14(1), R63, 2007] for applying the local lemma to random injections. In order to improve the constants in our results we use a version of the local lemma due to Bissacot, Fernández, Procacci, and Scoppola [preprint, arXiv:0910.1824].