论文标题
两分图中的不对称列表大小
Asymmetric list sizes in bipartite graphs
论文作者
论文摘要
给定具有零件$ a $和$ b $具有最高学位最高学位的两分图，分别为$δ_a$和$δ_b$，考虑一个列表分配，以便分别为每个顶点$ a $ a或$ b $中的每个顶点列出了$ k_a $或$ k_b $的颜色列表。 我们证明了一些一般的条件，以$δ_a$，$δ_b$，$ k_a $，$ k_b $表示，以保证适当的着色，以便仅使用其列表中的颜色为每个顶点颜色。在非常不对称的情况下，这些在渐近上几乎是锋利的。我们特别建立了一个足够的条件，其中$Δ_A=δ_b=δ$，$ k_a = \logδ$和$ k_b =（1+o（1））Δ/\logδ$ as $Δ\ to \ to \ infty $。这相当于从1998年克里维尔维奇（Krivelevich）和第一作者开始的猜想方面的部分进步。 我们还通过完整的情况和近似Steiner系统的极端大小之间的有趣联系来得出一些必要的条件。我们表明，对于完整的两分图，这些条件在参数空间的很大一部分中渐近几乎是锐利的。这引起了以下内容。 在上面的设置中，我们猜想始终保证正确的列表着色 *如果$ k_a \geδ_a^\ varepsilon $和$ k_b \geΔ_b^\ varepsilon $用于任何$ \ varepsilon> 0 $提供$Δ_A$和$Δ_B$，则足够大; *如果$ k_a \ ge c \logδ_b$和$ k_b \ ge c \logδ_a$对于某些绝对常数$ c> 1 $;或者 *如果$δ_a=δ_b=δ$和$ k_b \ ge c（δ/\logΔ）^{1/k_a} \logΔ$对于某些绝对常数$ c> 0 $。 这些是Krivelevich和第一作者的上述猜想的不对称概括，如果为true，则接近可能。我们的一般足够条件为这些猜想提供了部分进步。
Given a bipartite graph with parts $A$ and $B$ having maximum degrees at most $Δ_A$ and $Δ_B$, respectively, consider a list assignment such that every vertex in $A$ or $B$ is given a list of colours of size $k_A$ or $k_B$, respectively. We prove some general sufficient conditions in terms of $Δ_A$, $Δ_B$, $k_A$, $k_B$ to be guaranteed a proper colouring such that each vertex is coloured using only a colour from its list. These are asymptotically nearly sharp in the very asymmetric cases. We establish one sufficient condition in particular, where $Δ_A=Δ_B=Δ$, $k_A=\log Δ$ and $k_B=(1+o(1))Δ/\logΔ$ as $Δ\to\infty$. This amounts to partial progress towards a conjecture from 1998 of Krivelevich and the first author. We also derive some necessary conditions through an intriguing connection between the complete case and the extremal size of approximate Steiner systems. We show that for complete bipartite graphs these conditions are asymptotically nearly sharp in a large part of the parameter space. This has provoked the following. In the setup above, we conjecture that a proper list colouring is always guaranteed * if $k_A \ge Δ_A^\varepsilon$ and $k_B \ge Δ_B^\varepsilon$ for any $\varepsilon>0$ provided $Δ_A$ and $Δ_B$ are large enough; * if $k_A \ge C \logΔ_B$ and $k_B \ge C \logΔ_A$ for some absolute constant $C>1$; or * if $Δ_A=Δ_B = Δ$ and $ k_B \ge C (Δ/\logΔ)^{1/k_A}\log Δ$ for some absolute constant $C>0$. These are asymmetric generalisations of the above-mentioned conjecture of Krivelevich and the first author, and if true are close to best possible. Our general sufficient conditions provide partial progress towards these conjectures.
