Coloring hypergraphs of low connectivity

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) \leq \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) \leq \lambda (G) + 1$. In this paper, we show that a hypergraph $G$ with $\lambda (G) \geq 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 \geq 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) \leq 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$.

Keywords

hypergraph coloring, hypergraph connectivity, Brooks’ Theorem

2010 Mathematics Subject Classification

05C15

Full Text (PDF format)

Received 2 July 2018

Accepted 8 January 2021

Published 31 January 2022