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

DOI10.1016/J.DISC.2014.01.014MaRDI QIDQ2439129zbMATH OpenOpenAlexFDO

Authors Michael A. Henning, Christian Löwenstein

Publication date 7 March 2014

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.4851

zbMATH Keywords

edge coloringhypergraphmatchingsmultigraphtransversal

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15)

Abstract: For $kge2$, let $H$ be a $k$-uniform hypergraph on $n$ vertices and $m$ edges. The transversal number $au(H)$ of $H$ is the minimum number of vertices that intersect every edge. Chv'{a}tal and McDiarmid [Combinatorica 12 (1992), 19--26] proved that $au(H)le(n+leftlfloorfrack2ightfloorm)/(leftlfloorfrac3k2ightfloor)$. When $k=3$, the connected hypergraphs that achieve equality in the Chv'{a}tal-McDiarmid Theorem were characterized by Henning and Yeo [J. Graph Theory 59 (2008), 326--348]. In this paper, we characterize the connected hypergraphs that achieve equality in the Chv'{a}tal-McDiarmid Theorem for $k=2$ and for all $kge4$.

Recommendations

• Hypergraphs with large transversal number and with edge sizes at least four
• Hypergraphs with large transversal number
• Linear hypergraphs with large transversal number and maximum degree two
• A sharp upper bound for the transversal number of k-uniform connected hypergraphs with given size
• Transversal numbers of uniform hypergraphs

Cites work

• A Theorem on Coloring the Lines of a Network
• An upper bound for the transversal numbers of 4-uniform hypergraphs
• Covering all cliques of a graph
• Hypergraphs with large transversal number
• Hypergraphs with large transversal number and with edge sizes at least 3
• Hypergraphs with large transversal number and with edge sizes at least four
• Small transversals in hypergraphs
• Strong transversals in hypergraphs and double total domination in graphs
• Total domination of graphs and small transversals of hypergraphs

Cited in

(15)

• On upper transversals in 3-uniform hypergraphs
• A note on fractional disjoint transversals in hypergraphs
• Affine planes and transversals in 3-uniform linear hypergraphs
• Bounds on upper transversals in hypergraphs
• Transversals and independence in linear hypergraphs with maximum degree two
• Upper transversals in hypergraphs
• A characterization of hypergraphs with large domination number
• Transversal game on hypergraphs and the \(\frac{3}{4}\)-conjecture on the total domination game
• The Fano plane and the strong independence ratio in hypergraphs of maximum degree 3
• Bounds on the game transversal number in hypergraphs
• Domination and total domination in hypergraphs
• Hypergraphs with large transversal number and with edge sizes at least four
• Transversals in regular uniform hypergraphs
• The Tuza–Vestergaard Theorem
• Extensions and applications of the Tuza-Vestergaard theorem

This page was built for publication: A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid theorem

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