Covering Graphs by Monochromatic Trees and Helly-Type Results for Hypergraphs
dc.contributor.author
Bucić, Matija
dc.contributor.author
Korándi, Dániel
dc.contributor.author
Sudakov, Benny
dc.date.accessioned
2021-07-21T08:36:31Z
dc.date.available
2021-07-15T10:37:34Z
dc.date.available
2021-07-21T08:36:31Z
dc.date.issued
2021
dc.identifier.issn
0209-9683
dc.identifier.issn
1439-6912
dc.identifier.other
10.1007/s00493-020-4292-9
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/495001
dc.description.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 Cirao, Letzter and Sahasrabudhe.
en_US
dc.language.iso
en
en_US
dc.publisher
Springer
en_US
dc.title
Covering Graphs by Monochromatic Trees and Helly-Type Results for Hypergraphs
en_US
dc.type
Journal Article
dc.date.published
2021-04-21
ethz.journal.title
Combinatorica
ethz.journal.volume
41
en_US
ethz.pages.start
319
en_US
ethz.pages.end
352
en_US
ethz.grant
Problems in Extremal and Probabilistic Combinatorics
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.publication.place
Heidelberg
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02502 - Institut für Operations Research / Institute for Operations Research::03993 - Sudakov, Benjamin / Sudakov, Benjamin
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02502 - Institut für Operations Research / Institute for Operations Research::03993 - Sudakov, Benjamin / Sudakov, Benjamin
ethz.grant.agreementno
196965
ethz.grant.fundername
SNF
ethz.grant.funderDoi
10.13039/501100001711
ethz.grant.program
Projekte MINT
ethz.date.deposited
2021-07-15T10:38:22Z
ethz.source
WOS
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2021-07-21T08:36:37Z
ethz.rosetta.lastUpdated
2022-03-29T10:33:58Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Covering%20Graphs%20by%20Monochromatic%20Trees%20and%20Helly-Type%20Results%20for%20Hypergraphs&rft.jtitle=Combinatorica&rft.date=2021&rft.volume=41&rft.spage=319&rft.epage=352&rft.issn=0209-9683&1439-6912&rft.au=Buci%C4%87,%20Matija&Kor%C3%A1ndi,%20D%C3%A1niel&Sudakov,%20Benny&rft.genre=article&rft_id=info:doi/10.1007/s00493-020-4292-9&
Files in this item
| Files | Size | Format | Open in viewer |
|---|---|---|---|
|
There are no files associated with this item. |
|||
Publication type
-
Journal Article [132254]