Covering Graphs by Monochromatic Trees and Helly-Type Results for Hypergraphs

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

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 Cirão, Letzter and Sahasrabudhe.

Original languageEnglish (US)
Pages (from-to)319-352
Number of pages34
JournalCombinatorica
Volume41
Issue number3
DOIs
StatePublished - Jun 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Covering Graphs by Monochromatic Trees and Helly-Type Results for Hypergraphs'. Together they form a unique fingerprint.

Cite this