Coloring hypergraphs of low connectivity

For a hypergraph $G$, let $\chi (G),\mathrm{\Delta }(G),$ and $\lambda (G)$ denote the chromatic number, the maximum degree, and the maximum local edge connectivity of $G$, respectively. A result of Rhys Price Jones from 1975 says that every connected hypergraph $G$ satisfies $\chi (G)\le \mathrm{\Delta }(G)+1$ and equality holds if and only if $G$ is a complete graph, an odd cycle, or $G$ has just one (hyper-)edge. By a result of Bjarne Toft from 1970 it follows that every hypergraph $G$ satisfies $\chi (G)\le \lambda (G)+1$. In this paper, we show that a hypergraph $G$ with $\lambda (G)\ge 3$ satisfies $\chi(G) = \lambda(G)

• 1$ifandonlyif$G$containsablockwhichbelongstoafamily$$\mathcal{H}$_{\lambda(G)}$\mathrm{.}Theclass$$\mathcal{H}$_3$ is the smallest family which contains all odd wheels and is closed under taking Haj'os joins. For $k \geq 4$,thefamily$$\mathcal{H}$_k$ is the smallest that contains all complete graphs $K_{k+1}$ and is closed under Haj'os joins. For the proofs of the above results we use critical hypergraphs. A hypergraph $G$ is called $(k+1)$-critical if $\chi (G)=k+1$, but $\chi (H)\le k$ whenever $H$ is a proper subhypergraph of $G$. We give a characterization of $(k+1)$-critical hypergraphs having a separating edge set of size $k$ as well as a a characterization of $(k+1)$-critical hypergraphs having a separating vertex set of size $2$.