𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hypergraph families with bounded edge cover or transversal number

✍ Scribed by A. Gyárfás; J. Lehel

Book ID
110564241
Publisher
Springer-Verlag
Year
1983
Tongue
English
Weight
465 KB
Volume
3
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Hypergraphs with large transversal numbe
Hypergraphs with large transversal number and with edge sizes at least 3
✍ Michael A. Henning; Anders Yeo 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 264 KB

## Abstract It is shown in several manuscripts [Discrete Math 86 (1990), 117–126; Combinatorica 12 (1992), 19–26] that every hypergraph of order __n__ and size __m__ with edge sizes at least 3 has a transversal of size at most (__n__ + __m__)/4. In this article, we characterize the connected such h

Tight upper bound on the number of edges
Tight upper bound on the number of edges in a bipartite K3,3-free or K5-free graph with an application
✍ Zhi-Zhong Chen; Shiqing Zhang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 68 KB

We show that an n-vertex bipartite K 3,3 -free graph with n 3 has at most 2n -4 edges and that an n-vertex bipartite K 5 -free graph with n 5 has at most 3n -9 edges. These bounds are also tight. We then use the bound on the number of edges in a K 3,3 -free graph to extend two known NC algorithms fo