Article ID Journal Published Year Pages File Type
419723 Discrete Applied Mathematics 2013 7 Pages PDF
Abstract

Let HH be a dd-uniform hypergraph that has a geometric realization in Rd. We show that there is a set CC of edges of HH that meets all copies of the complete subhypergraph Kd+1d in HH with |C|≤(⌈d2⌉+1)ν(H), where ν(H)ν(H) denotes the maximum size of a set of pairwise edge-disjoint copies of Kd+1d in HH. This generalizes a result of Tuza on planar graphs. For d=3d=3 we also prove two fractional weakenings of the same statement for arbitrary 3-uniform hypergraphs.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,