Skip to Main content Skip to Navigation
Conference papers

Connected τ -critical hypergraphs of minimal size

Abstract : A hypergraph $\mathscr{H}$ is $τ$ -critical if $τ (\mathscr{H}-E) < τ (\mathscr{H})$ for every edge $E ∈\mathscr{H}$, where $τ (\mathscr{H})$ denotes the transversal number of $\mathscr{H}$. It can be shown that a connected $τ$ -critical hypergraph $\mathscr{H}$ has at least $2τ (\mathscr{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 $\mathscr{H}$ with exactly $2τ (\mathscr{H)}-1$ edges. We prove that such hypergraphs have at least $2τ (\mathscr{H})-1$ vertices, and characterise those with $2τ (\mathscr{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 $\mathscr{H}$ with fewer than $2τ (\mathscr{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.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 11:36:58 AM
Last modification on : Monday, August 8, 2022 - 5:38:05 PM
Long-term archiving on: : Sunday, November 15, 2015 - 10:58:34 AM


Publisher files allowed on an open archive




Matěj Stehlík. Connected τ -critical hypergraphs of minimal size. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.157-160, ⟨10.46298/dmtcs.3397⟩. ⟨hal-01184353⟩



Record views


Files downloads