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

Autor(es)

Boettcher, Julia ^[1] ; Kohayakawa, Yoshiharu ^[1] ; Procacci, Aldo ^[2]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil

^[2] Univ Fed Minas Gerais, Dept Matemat, BR-30161970 Belo Horizonte, MG - Brazil

• Tipo de documento: Artigo Científico
• Fonte: RANDOM STRUCTURES & ALGORITHMS; v. 40, n. 4, p. 425-436, JUL 2012.
• Citações Web of Science: 14

Resumo

Let G be a graph on n vertices with maximum degree ?. We use the Lovasz local lemma to show the following two results about colourings ? of the edges of the complete graph Kn. If for each vertex v of Kn 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 Kn which is properly edge-coloured by ?. This improves on a result of Alon, Jiang, Miller, and Pritikin {[}Random Struct. Algorithms 23(4), 409433, 2003]. On the other hand, if ? assigns each colour to at most n/(51?2) edges of Kn, then there is a copy of G in Kn 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 Szekely {[}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, Fernandez, Procacci, and Scoppola {[}preprint, arXiv:0910.1824]. (c) 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 425436, 2012 (AU)

• Processo FAPESP: 09/17831-7 - Problemas de imersão e empacotamento em teoria extremal dos grafos
• Beneficiário: Julia Boettcher
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado