Edge-colouring graphs with local list sizes

Abstract

The famous List Colouring Conjecture from the 1970s states that for every graph $G$ the chromatic index of $G$ is equal to its list chromatic index. In 1996 in a seminal paper, Kahn proved that the List Colouring Conjecture holds asymptotically. Our main result is a local generalization of Kahn's theorem. More precisely, we show that, for a graph $G$ with sufficiently large maximum degree $\Delta$ and minimum degree $\delta \ge {\ln }^{25}\Delta$, the following holds: for every assignment of lists of colours to the edges of $G$, such that $|L(e)|\ge (1+o(1))\cdot \max \left\{\mathrm{deg}(\mathrm{u}),\mathrm{deg}(\mathrm{v})\right\}$ for each edge $e=uv$, there is an $L$-edge-colouring of $G$. Furthermore, Kahn showed that the List Colouring Conjecture holds asymptotically for linear, $k$-uniform hypergraphs, and recently Molloy generalized Kahn's original result to correspondence colouring as well as its hypergraph generalization. We prove local versions of all of these generalizations by showing a weighted version that simultaneously implies all of our results.

25 pages, Accepted to JCTB

Cited by in corpus (1)

• Local girth choosability of planar graphs