Journal of Combinatorics
Volume 7 (2016)
Guest editors: Rong Luo and Cun-Quan Zhang
Decomposable and indecomposable critical hypergraphs
Pages: 423 – 451
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$.
Published 23 February 2016