论文标题
带有本地列表大小的边缘色图
Edge-colouring graphs with local list sizes
论文作者
论文摘要
1970年代的著名列表着色猜想指出，对于$ g $的每张图$ g $，$ g $的色度等于其列表的彩色索引。 1996年，卡恩（Kahn）在一份开创性的论文中证明了列表着色猜想是渐近地持有的。我们的主要结果是对卡恩定理的本地概括。更准确地说，我们表明，对于具有足够大的最高度$δ$和最低度$δ\ geq \ geq \ ln^{25}Δ$的图形$ g $，以下内容：对于$ g $的颜色列表的每一个分配， \ geq（1+o（1））\ cdot \ max \ max \ left \ {\ rm {deg}（u），\ rm {deg}（v）（v）（v）\ right \} $ for enge $ e = uv $，有$ l $ - $ l $ g $ g $。此外，卡恩（Kahn）表明，列表着色猜想对线性，$ k $均匀的超图和最近的Molloy概括性Kahn的最初结果均无含量，以及其超透明概括。我们通过显示一个同时暗示我们所有结果的加权版本来证明所有这些概括的本地版本。
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 $δ\geq \ln^{25} Δ$, the following holds: for every assignment of lists of colours to the edges of $G$, such that $|L(e)| \geq (1+o(1)) \cdot \max\left\{\rm{deg}(u),\rm{deg}(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.
