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

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

doi:10.1007/s00493-020-4292-9

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

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

Research output: Contribution to journal › Article › peer-review

2 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 language	English (US)
Pages (from-to)	319-352
Number of pages	34
Journal	Combinatorica
Volume	41
Issue number	3
DOIs	https://doi.org/10.1007/s00493-020-4292-9
State	Published - Jun 2021
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-020-4292-9

Cite this

@article{86229e34de9044dfa3a54c165645da31,

title = "Covering Graphs by Monochromatic Trees and Helly-Type Results for Hypergraphs",

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{\~a}o, Letzter and Sahasrabudhe.",

author = "Matija Buci{\'c} and D{\'a}niel Kor{\'a}ndi and Benny Sudakov",

note = "Publisher Copyright: {\textcopyright} 2021, J{\'a}nos Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.",

year = "2021",

month = jun,

doi = "10.1007/s00493-020-4292-9",

language = "English (US)",

volume = "41",

pages = "319--352",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "3",

}

TY - JOUR

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

AU - Bucić, Matija

AU - Korándi, Dániel

AU - Sudakov, Benny

PY - 2021/6

Y1 - 2021/6

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

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

UR - http://www.scopus.com/inward/record.url?scp=85105003291&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85105003291&partnerID=8YFLogxK

U2 - 10.1007/s00493-020-4292-9

DO - 10.1007/s00493-020-4292-9

M3 - Article

AN - SCOPUS:85105003291

SN - 0209-9683

VL - 41

SP - 319

EP - 352

JO - Combinatorica

JF - Combinatorica

IS - 3

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this