Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Covering Graphs by Monochromatic Trees and Helly-Type Results for Hypergraphs
 
research article

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

Bucic, Matija
•
Korandi, Daniel  
•
Sudakov, Benny
April 21, 2021
Combinatorica

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.

  • Details
  • Metrics
Type
research article
DOI
10.1007/s00493-020-4292-9
Web of Science ID

WOS:000642048500002

Author(s)
Bucic, Matija
Korandi, Daniel  
Sudakov, Benny
Date Issued

2021-04-21

Publisher

SPRINGER HEIDELBERG

Published in
Combinatorica
Volume

41

Start page

319

End page

352

Subjects

Mathematics

•

05c15

•

05c65

•

05c80

•

05d15

•

05d40

•

rysers conjecture

•

cycles

•

transversals

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
May 22, 2021
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/178203
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés