A Brooks Type Theorem for the Maximum Local Edge Connectivity

Abstract

For a graph $G$, let $\chi(G)$ and $\lambda(G)$ denote the chromatic number of $G$ and the maximum local edge connectivity of $G$, respectively. A result of Dirac implies that every graph $G$ satisfies $\chi(G)\leq \lambda(G)+1$. In this paper we characterize the graphs $G$ for which $\chi(G)=\lambda(G)+1$. The case $\lambda(G)=3$ was already solved by Aboulker, Brettell, Havet, Marx, and Trotignon. We show that a graph $G$ with $\lambda(G)=k\geq 4$ satisfies $\chi(G)=k+1$ if and only if $G$ contains a block which can be obtained from copies of $K_{k+1}$ by repeated applications of the Hajós join.