论文标题
列出平面图和相关类的多色
List Multicoloring of Planar Graphs and Related Classes
论文作者
论文摘要
对于正整数$ a $和$ b $，图$ g $是$（a：b）$ - 如果对于每种$ a $ a $颜色的列表的分配给$ g的顶点，则可以从其列表中的一组$ b $的颜色上色，以使相邻的顶点与分离的颜色相关。我们表明，对于正整数$ a $ a和$ b $，每个两部分平面图都是$（a：b）$ - 可chosable如果iff $ \ frac {a} {a} {b} {b} \ ge 3 $。对于一般平面图，我们表明，如果$ \ frac {a} {b} <4 \ frac {2} {5} $，则存在一个不是$（a：b）$的平面图，因此可以根据X. Zhu的结果进行改进，从而改善了X. Zhu的结果。最后，我们表明，每个$ k_5 $ -minor的图形都是$（a：b）$ - 可chosable iff $ \ frac {a} {b} {b} \ ge 5 $。一路上，我们提到了一些开放问题。
For positive integers $a$ and $b$, a graph $G$ is $(a:b)$-choosable if, for each assignment of lists of $a$ colors to the vertices of $G,$ each vertex can be colored with a set of $b$ colors from its list so that adjacent vertices are colored with disjoint sets. We show that for positive integers $a$ and $b$, every bipartite planar graph is $(a:b)$-choosable iff $\frac{a}{b} \ge 3$. For general planar graphs, we show that if $\frac{a}{b} < 4\frac{2}{5}$, then there exists a planar graph that is not $(a:b)$-choosable, thus improving on a result of X. Zhu, which had $4\frac{2}{9}$. Lastly, we show that every $K_5$-minor-free graph is $(a:b)$-choosable iff $\frac{a}{b} \ge 5$. Along the way, we mention some open problems.
