Bounding the vertex cover number of a hypergraph
type: Item
instance of: scholarly article
title: Bounding the vertex cover number of a hypergraph
zbMATH Open document ID: 0796.05072
DOI: 10.1007/BF01305948
author: Guoli Ding
author: Paul Seymour
author: Peter Winkler
published in: Combinatorica
publication date: 1994-09-15T00:00:00Z
review text: For a hypergraph \(H\), let \(\tau (H)\) be the minimum \(k\) such that some set of \(k\) vertices meets all the edges and let \(\nu (H)\) be the maximum \(k\) such that some \(k\) edges are pairwise disjoint. Let \(\lambda (H)\) be the maximum \(k \geq 2\) such that the incidence matrix of \(H\) has as a submatrix the transpose of the incidence matrix of the complete graph \(K_ k\). This paper shows that \(\tau (H)\) is bounded above by a function of \(\nu (H)\) and \(\lambda (H)\), and indeed that if \(\lambda (H)\) is bounded by a constant then \(\tau (H)\) is at most a polynomial function of \(\nu (H)\).
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 567470
zbMATH Keywords: vertex cover number
zbMATH Keywords: hypergraph
zbMATH Keywords: incidence matrix
MaRDI profile type: Publication
cites work: On obstructions to small face covers in planar graphs
cites work: Learnability and the Vapnik-Chervonenkis dimension
cites work: Notes on the Ramsey number N(3,3,3,3)
cites work: \(\epsilon\)-nets and simplex range queries
cites work: Almost tight bounds for \(\epsilon\)-nets
cites work: Distribution inequalities for the binomial law
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
description: scientific article; zbMATH DE number 567470