Covering 3-coloured random graphs with monochromatic trees

Main Article Content

Yoshiharu Kohayakawa Walner Mendonça Guilherme Mota Bjarne Schülke

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].

Article Details

How to Cite
Kohayakawa, Y., Mendonça, W., Mota, G., & Schülke, B. (2019). Covering 3-coloured random graphs with monochromatic trees. Acta Mathematica Universitatis Comenianae, 88(3), 871-875. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1310/739
Section
EUROCOMB 2019