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

DOI10.1007/S00493-020-4292-9MaRDI QIDQ2043761zbMATH OpenOpenAlexFDO

Authors Dániel Korándi, Matija Bucić, Benny Sudakov

Publication date 3 August 2021

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.05055

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Abstract: How many monochromatic paths, cycles or general trees does one need to cover all vertices of a given

r

-edge-coloured graph

G

? These problems were introduced in the 1960s and were intensively studied by various researchers over the last 50 years. In this paper, we establish a connection between this problem and the following natural Helly-type question in hypergraphs. Roughly speaking, this question 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. We 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 by Bal and DeBiasio, Kohayakawa, Mota and Schacht, Lang and Lo, and Gir~ao, Letzter and Sahasrabudhe.

Review text

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.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Covering graphs by monochromatic trees and Helly-type results for hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2043761)