COVERING 3-COLOURED RANDOM GRAPHS WITH MONOCHROMATIC TREES

Author(s)

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

Affiliation

^[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

• Document type: Journal article
• Source: ACTA MATHEMATICA UNIVERSITATIS COMENIANAE; v. 88, n. 3, p. 871-875, 2019.
• Web of Science Citations: 0

Abstract

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)

• FAPESP's process: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
• Grantee: Carlos Eduardo Ferreira
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Research Grants - Young Investigators Grants