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

zbMATH Keywords

treecoveringhypergraphsHelly

Mathematics Subject Classification ID

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

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.

Recommendations

• Covering 3-edge-colored random graphs with monochromatic trees
• The complexity for partitioning graphs by monochromatic trees, cycles and paths
• Vertex covers by monochromatic pieces -- a survey of results and problems
• Partitioning by monochromatic trees
• Monochromatic cycle covers in random graphs
• scientific article; zbMATH DE number 4154488
• Vertex coverings by monochromatic cycles and trees
• Monochromatic cycle partitions in random graphs
• scientific article; zbMATH DE number 1185305
• Monochromatic tree covers and Ramsey numbers for set-coloured graphs

Cites work

• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 4065037 (Why is no real title available?)
• scientific article; zbMATH DE number 15152 (Why is no real title available?)
• scientific article; zbMATH DE number 3616474 (Why is no real title available?)
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• scientific article; zbMATH DE number 3214278 (Why is no real title available?)
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• A Problem in Graph Theory
• A family of extremal hypergraphs for Ryser's conjecture
• A note on intersecting hypergraphs with large cover number
• An extremal problem for sets with applications to graph theory
• An improved bound for the monochromatic cycle partition number
• Combinatorial theorems in sparse random sets
• Exact bounds for some hypergraph saturation problems
• Extremal results for random discrete structures
• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
• Large monochromatic components and long monochromatic cycles in random hypergraphs
• Local constraints ensuring small representing sets
• Matchings and covers in hypergraphs
• Minimum degree conditions for monochromatic cycle partitioning
• Monochromatic cycle covers in random graphs
• Monochromatic cycle partitions in random graphs
• Multipartite hypergraphs achieving equality in Ryser's conjecture
• On Ryser's conjecture
• On Ryser's conjecture for linear intersecting multipartite hypergraphs
• On generalized graphs
• On the ratio of optimal integral and fractional covers
• Partitioning a graph into monochromatic connected subgraphs
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Partitioning random graphs into monochromatic components
• Ryser's conjecture for tripartite 3-graphs
• Small transversals in uniform hypergraphs
• The probabilistic method
• Transversals in uniform hypergraphs with property (7, 2)
• Transversals in uniform hypergraphs with property \((p,2)\)
• Vertex coverings by monochromatic cycles and trees
• Vertex covers by monochromatic pieces -- a survey of results and problems
• τ–Critical Hypergraphs and the Helly Property

Cited in

(6)

• Generalizations and strengthenings of Ryser's conjecture
• Covering 3-edge-colored random graphs with monochromatic trees
• Vertex coverings by monochromatic cycles and trees
• Monochromatic tree covers and Ramsey numbers for set-coloured graphs
• Covering random graphs with monochromatic trees
• Cover \(k\)-uniform hypergraphs by monochromatic loose paths

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)