论文标题
$ 3 $选择关键图的多重列表着色
Multiple list colouring of $3$-choice critical graphs
论文作者
论文摘要
如果$ g $不是$ 2 $ -Choosable，则图$ G $称为$ 3 $ - 选择至关重要的，但是任何适当的子图都是$ 2 $ - choosable。 Voigt在[on list colorings and oflesabils of Graphs，HabilitationsSchrift，tu Ilmenau（1998）]中给出了$ 3 $ - 选择关键图的特征。 Voigt猜想，如果$ g $是两部分$ 3 $ - 选择性关键图，则$ g $是$ $（400万，200万）$ - 可用于每个整数$ m $ $。在[ON（4，2） - 可选图中，Meng，Puleo和Zhu所反驳了这一猜想。 They showed that if $G=Θ_{r,s,t}$ where $r,s,t$ have the same parity and $\min\{r,s,t\} \ge 3$, or $G=Θ_{2,2,2,2p}$ with $p \ge 2$, then $G$ is bipartite $3$-choice critical, but not $(4,2)$-choosable.另一方面，所有其他两部分3-Choice关键图形均为$（4,2）$ - 可chosable。本文增强了Meng，Puleo和Zhu的结果，并表明所有其他两部分的$ 3 $ - 选择性关键图形为$（400万，200万）$ - 可用于每个整数$ M $ $。
A graph $G$ is called $3$-choice critical if $G$ is not $2$-choosable but any proper subgraph is $2$-choosable. A characterization of $3$-choice critical graphs was given by Voigt in [On list Colourings and Choosability of Graphs, Habilitationsschrift, Tu Ilmenau(1998)]. Voigt conjectured that if $G$ is a bipartite $3$-choice critical graph, then $G$ is $(4m, 2m)$-choosable for every integer $m$. This conjecture was disproved by Meng, Puleo and Zhu in [On (4, 2)-Choosable Graphs, Journal of Graph Theory 85(2):412-428(2017)]. They showed that if $G=Θ_{r,s,t}$ where $r,s,t$ have the same parity and $\min\{r,s,t\} \ge 3$, or $G=Θ_{2,2,2,2p}$ with $p \ge 2$, then $G$ is bipartite $3$-choice critical, but not $(4,2)$-choosable. On the other hand, all the other bipartite 3-choice critical graphs are $(4,2)$-choosable. This paper strengthens the result of Meng, Puleo and Zhu and shows that all the other bipartite $3$-choice critical graphs are $(4m,2m)$-choosable for every integer $m$.
