Abstract
For k≥2, let H be a k-uniform hypergraph on n vertices and m edges. The transversal number τ(H) of H is the minimum number of vertices that intersect every edge. Chvátal and McDiarmid (1992) proved that τ(H)≤(n+Šk2m)/(aŠ3k2). When k=3, the connected hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem were characterized by Henning and Yeo (2008). In this paper, we characterize the connected hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem for k=2 and for all k≥4.
Original language | English |
---|---|
Pages (from-to) | 69-75 |
Number of pages | 7 |
Journal | Discrete Mathematics |
Volume | 323 |
Issue number | 1 |
DOIs | |
Publication status | Published - 28 May 2014 |
Keywords
- Edge coloring
- Hypergraph
- Matchings
- Multigraph
- Transversal
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics