Covering graphs by monochromatic trees and Helly-type results for hypergraphs

DOI10.1007/S00493-020-4292-9zbMATH Open1488.05350arXiv1902.05055OpenAlexW3155051756MaRDI QIDQ2043761FDOQ2043761

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

Publication date: 3 August 2021

Published in: Combinatorica (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1902.05055

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
• 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

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)

Cites Work

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

Cited In (5)

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

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)