A Brooks-type theorem for the k-choosability of graphs with maximum local edge-connectivity k

Abstract

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 maximum local edge-connectivity $k$ is $k$-choosable if and only if it is not in ${\mathcal{H}}_k$. On the other hand, deciding $k$-choosability when restricted to graphs with maximum local edge-connectivity $k$ (that might not be $2$-connected) is ${\Pi }_2$-complete. To prove the former result, we first prove several generalisations of a well-known characterisation of degree-choosability; these may be of independent interest.

arXiv comment54 pages including appendix, 16 figures