Covering a hypergraph of subgraphs

DOI10.1016/S0012-365X(02)00427-2MaRDI QIDQ1850010zbMATH OpenFDO

Authors Noga Alon

Publication date 2 December 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(02)00427-2

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Let \(H\) be a collection of subgraphs of a tree \(G\), each of which has at most \(d\) connected components. Let \(\nu(H)\) be the maximum number of members of \(H\), no two of which share a common vertex, and let \(\tau(H)\) be the minimum cardinality of a set of vertices of \(G\) that intersects all members of \(H\). The paper shows that \(\tau(H)\leq 2d^2\nu(H)\). This result is then extended to the situation where \(G\) is not a tree but it has a bounded tree-width.

Recommendations

• Bounding the vertex cover number of a hypergraph
• On the tree cover number of a graph
• KKM -- a topological approach for trees
• A tree version of Kőnig's theorem
• Covering non-uniform hypergraphs

Cited in

(20)

• Bounding the vertex cover number of a hypergraph
• Covering the edges of a graph by a prescribed tree with minimum overlap
• The (p, q) property in families of d-intervals and d-trees
• A tree version of Kőnig's theorem
• Piercing numbers in approval voting
• Packing and covering with balls on Busemann surfaces
• Recent techniques and results on the Erdős-Pósa property
• KKM -- a topological approach for trees
• Partial covering of hypergraphs
• Red-blue clique partitions and (1-1)-transversals
• scientific article; zbMATH DE number 3887743 (Why is no real title available?)
• Erdös-Pósa Property of Obstructions to Interval Graphs
• Algorithms for the minimum edge cover of \(H\)-subgraphs of a graph
• scientific article; zbMATH DE number 3972916 (Why is no real title available?)
• Using Brouwer’s Fixed Point Theorem
• Quadratic forms on graphs
• Overlaying a hypergraph with a graph with bounded maximum degree
• Erdős–Pósa property of obstructions to interval graphs
• Fractional covers and matchings in families of weighted \(d\)-intervals
• Universality for graphs with bounded density

This page was built for publication: Covering a hypergraph of subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850010)