





















For a hypergraph $G$, let $χ(G), Δ(G),$ and $λ(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 $χ(G) \leq Δ(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 $χ(G) \leq λ(G) + 1$. In this paper, we show that a hypergraph $G$ with $λ(G) \geq 3$ satisfies $χ(G) = λ(G) + 1$ if and only if $G$ contains a block which belongs to a family $\mathcal{H}_{λ(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 $χ(G)=k+1$, but $χ(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$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。