DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Connected τ-critical hypergraphs of minimal size

Matěj Stehlík


A hypergraph H is τ-critical if τ(H-E) < τ(H) for every edge E ∈H, where τ(H) denotes the transversal number of H. It can be shown that a connected τ-critical hypergraph H has at least 2τ(H)-1 edges; this generalises a classical theorem of Gallai on χ-vertex-critical graphs with connected complements. In this paper we study connected τ-critical hypergraphs H with exactly 2τ(H)-1 edges. We prove that such hypergraphs have at least 2τ(H)-1 vertices, and characterise those with 2τ(H)-1 vertices using a directed odd ear decomposition of an associated digraph. Using Seymour's characterisation of χ-critical 3-chromatic square hypergraphs, we also show that a connected square hypergraph H with fewer than 2τ(H) edges is τ-critical if and only if it is χ-critical 3-chromatic. Finally, we deduce some new results on χ-vertex-critical graphs with connected complements.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional