Minimal Connected τ-Critical Hypergraphs

摘要

A hypergraph is τ-critical if τ( −{E})<τ( ) for every edge E ∈ , where τ( ) denotes the transversal number of . We show that if is a connected τ-critical hypergraph, then −{E} can be partitioned into τ( )−1 stars of size at least two, for every edge E ∈ . An immediate corollary is that a connected τ-critical hypergraph has at least 2τ( )−1 edges. This extends, in a very natural way, a classical theorem of Gallai on colour-critical graphs, and is equivalent to a theorem of Füredi on t-stable hypergraphs. We deduce a lower bound on the size of τ-critical hypergraphs of minimum degree at least two.