Covering graphs by monochromatic trees and Helly-type results for hypergraphs (Q2043761)

This interesting paper contains many results. First, the authors present some preliminary results and tools, mostly simple properties of random graphs. After this they establish a connection between the problem of determining how many monochromatic paths or monochromatic components does one need to cover all vertices of a given \(r\)-edge-colored graph \(G\) and a natural Helly-type question in hypergraphs which asks for the maximum number of vertices needed to cover all the edges of a hypergraph \(H\) if it is known that any collection of a few edges of \(H\) has a small cover. They obtain quite accurate bounds for the hypergraph problem and use them to give some unexpected answers to several questions about covering graphs by monochromatic trees raised and studied earlier by several authors. In particular, they resolved a conjecture raised by \textit{D. Bal} and \textit{L. DeBiasio} [Electron. J. Comb. 24, No. 1, Research Paper P1.18, 25 p. (2017; Zbl 1355.05192)] by showing that if \(G\) is an \(r\)-colored graph on \(n\) vertices with \(\delta(G) \geq (1 - 2^{-r})n\), then the vertices of \(G\) can be covered by monochromatic components of distinct colors. Some open problems and an appendix in which the authors give an alternative perspective to the general hypergraph setting conclude the paper.