2020/07/29 by Bonamy, Marthe, Delcourt, Michelle, Lang, Richard +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2007.14944
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 Δ and minimum degree δ≥ ln25 Δ, the following holds: for every assignment of lists of colours to the edges of G, such that |L(e)| ≥ (1+o(1)) ⋅ max\\rmdeg(u),\rmdeg(v)\ 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.