Covering 3-coloured random graphs with monochromatic trees

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\gg \left(\frac{\ln n}{n}\right)^{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 Buci\'c, Kor\'andi and Sudakov [Covering random graphs by monochromatic trees and Helly-type results for hypergraphs, arXiv:1902.05055].