On point covers of multiple intervals and axis-parallel rectangles
type: Item
instance of: scholarly article
title: On point covers of multiple intervals and axis-parallel rectangles
zbMATH Open document ID: 0866.05046
DOI: 10.1007/BF01844847
author: Gyula Károlyi
author: Gábor Tardos
published in: Combinatorica
publication date: 1997-06-25T00:00:00Z
review text: Let \(H\) be a hypergraph on an underlying set \(X\). A set \(S \subset X\) is said to cover an edge \(E\) of \(H\) if it intersects \(E\). The transversal number \(\tau(H)\) is the minimum size of sets which cover all edges of \(H\). The packing number \(\nu(H)\) is the maximum number of sets of pairwise disjoint edges of \(H\). A hypergrah \(H\) on \(X\) is said to be rectangular if \(X\) can be placed in the plane so that every edge of \(H\) is of the form \(X \cap R\), where \(R\) is a suitable rectangle with sides parallel to the coordinate axes. The main result of the paper is the following: For any rectangular hypergraph \(H\), \(\tau(H) \leq 4 \nu(H)(\lfloor \log \nu(H) \rfloor +1)^2 \).
reviewed by: Toru Ishihara
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 936872
zbMATH Keywords: hypergraph
zbMATH Keywords: transversal number
zbMATH Keywords: packing number
zbMATH Keywords: rectangle
MaRDI profile type: Publication
cites work: Bounding the vertex cover number of a hypergraph
cites work: Covering boxes by points
cites work: Covering and coloring problems for relatives of intervals
cites work: Q3271426
cites work: On point covers of parallel rectangles
cites work: Transversals of 2-intervals, a topological approach
cites work: Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner
full work available at URL: https://doi.org/10.1007/bf01844847
OpenAlex ID: W1975233475
description: scientific article; zbMATH DE number 936872