Journal of Combinatorics

Volume 7 (2016)

Number 2–3

Guest editors: Rong Luo and Cun-Quan Zhang

Decomposable and indecomposable critical hypergraphs

Pages: 423 – 451



Michael Stiebitz (Inst. of Math., Technische Universität, Ilmenau, Germany)

Patrick Storch (Inst. of Math., Technische Universität, Ilmenau, Germany)

Bjarne Toft (University of Southern Denmark, IMADA, Odense, Denmark)


A hypergraph is $k$-critical if it has chromatic number $k$, but each of its proper subhypergraphs has a coloring with $k-1$ colors. In 1963 T. Gallai proved that every $k$-critical graph of order at most $2k-2$ is decomposable, that is, its complement is disconnected. We shall prove a counterpart of this result for critical hypergraphs. Based on this result we shall determine the minimum number of edges of a $k$-critical hypergraph of order $n$, provided that $k \leq n \leq 2k - 1$.

Full Text (PDF format)