COVERING 3-COLOURED RANDOM GRAPHS WITH MONOCHROMATIC TREES

Autor(es)

Kohayakawa, Y. ^[1] ; Mendonca, W. ^[2] ; Mota, G. ^[3] ; Schuelke, B. ^[4]

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

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

^[2] Inst Nacl Matemat Pura & Aplicada, Rio De Janeiro - Brazil

^[3] Univ Fed ABC, Ctr Matemat Comp & Cognicao, Santo Andre, SP - Brazil

^[4] Univ Hamburg, Fachbereich Math, Hamburg - Germany

• Tipo de documento: Artigo Científico
• Fonte: ACTA MATHEMATICA UNIVERSITATIS COMENIANAE; v. 88, n. 3, p. 871-875, 2019.
• Citações Web of Science: 0

Resumo

We investigate the problem of determining how many monochromatic trees are necessary to cover the vertices of an edge-coloured random graph. More precisely, we show that for p >> (lnn/n)(1/6) in any 3-colouring of the random graph G (n, p) we can find 3 monochromatic trees such that their union covers all vertices. This improves, for three colours, a result of Bucie, Korandi and Sudakov {[}Covering random graphs by monochromatic trees and Helly-type results for hypergraphs, arXiv:1902.05055] (AU)

• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores