Coloring hypergraphs of low connectivity

Abstract

For a hypergraph $G$, let $\chi (G),\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 \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$ if and only if $G$ contains a block which belongs to a family ${\mathcal{H}}_{\lambda (G)}$. The class ${\mathcal{H}}_3$ is the smallest family which contains all odd wheels and is closed under taking Hajós joins. For $k\ge 4$, the family ${\mathcal{H}}_k$ is the smallest that contains all complete graphs $K_{k+1}$ and is closed under Hajós 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$.