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

https://hal.inria.fr/hal-01184353
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:36:58 AM
Last modification on : Thursday, May 11, 2017 - 1:02:54 AM
Long-term archiving on: : Sunday, November 15, 2015 - 10:58:34 AM

File

dmAE0131.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184353, version 1

Collections

Citation

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. ⟨hal-01184353⟩

Share

Metrics

Record views

67

Files downloads

732