A Brooks type theorem for the maximum local edge connectivity (Q1753016): Difference between revisions

Summary: 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 \textit{P. Aboulker} et al. [J. Graph Theory 85, No. 4, 814--838 (2017; Zbl 1368.05040)]. 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.