A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem

Michael A. Henning, Christian Löwenstein

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)

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 languageEnglish
Pages (from-to)69-75
Number of pages7
JournalDiscrete Mathematics
Volume323
Issue number1
DOIs
Publication statusPublished - 28 May 2014

Keywords

  • Edge coloring
  • Hypergraph
  • Matchings
  • Multigraph
  • Transversal

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem'. Together they form a unique fingerprint.

Cite this