2010/07/21 by Julia Böttcher, Böttcher, Julia, Yoshiharu Kohayakawa +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1007.3767
openalex publication_date 2010/07/21 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
Let G be a graph on n vertices with maximum degree D. We use the Lovász local lemma to show the following two results about colourings c of the edges of the complete graph Kn. If for each vertex v of Kn the colouring c assigns each colour to at most (n-2)/22.4D2 edges emanating from v, then there is a copy of G in Kn which is properly edge-coloured by c. This improves on a result of Alon, Jiang, Miller, and Pritikin [Random Struct. Algorithms 23(4), 409-433, 2003]. On the other hand, if c assigns each colour to at most n/51D2 edges of Kn, then there is a copy of G in Kn such that each edge of G receives a different colour from c. 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].