A Brooks-type theorem for the k-choosability of graphs with maximum local edge-connectivity k
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908896269959168 |
|---|---|
| author | Bastida, Sam Brettell, Nick |
| author_facet | Bastida, Sam Brettell, Nick |
| contents | 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 $Π_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_17113 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Brooks-type theorem for the k-choosability of graphs with maximum local edge-connectivity k Bastida, Sam Brettell, Nick Combinatorics Discrete Mathematics 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 $Π_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. |
| title | A Brooks-type theorem for the k-choosability of graphs with maximum local edge-connectivity k |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2603.17113 |