{"id":"arxiv/2603.17113","url":"https://arxiv.org/abs/2603.17113","tags":["math.CO","cs.DM"],"score":0,"title":"A Brooks-type theorem for the k-choosability of graphs with maximum local edge-connectivity k","domain":"math.CO","source":"arxiv","authors":["Sam Bastida","Nick Brettell"],"reviews":0,"subject":"math.CO","summary":"For a graph $G$ with at least two vertices, the maximum local edge-connectivity of $G$ is the maximum number of edge-disjoint $(u,v)$-paths over all distinct pairs of vertices $(u,v)$ in $G$. Stiebitz and Toft (2018) proved a Brooks-type theorem for graphs with maximum local edge-connectivity $k$, showing that a graph with maximum local edge-connectivity $k$ is not $k$-colourable if and only if it has a block in $\\mathcal{H}_k$, which is the class of graphs that can be obtained by taking Hajós joins of copies of $K_{k+1}$ and, when $k=3$, odd wheels. We prove that a $2$-connected graph with…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-17","reactions":{}}