不含相邻短圈的平面图的 (3, 1)^*-可选性

(3, 1)^*-Choosability of Planar Graphs without Adjacent Short Cycles

图 G的一个颜色列表配置 L是指给 G中的每个顶点 v都分配一个可用色集 L(v)。 如果在映射 ?下对任意 v ∈ V (G)均满足 ?(v) ∈ L(v),使得在 v的邻点中至多有 d个顶点的颜色为 ?(v),那 么我们称 G是 (L, d)?-可染的。 如果对任意颜色列表配置 L = {L(v)||L(v)| ≥ k, v ∈ V (G)}, G都 是 (L, d)?-可染的,那么我们就称 G 是 (k, d)?-可选的。 Xu 和Zhang 猜想:不含相邻 3-圈的平 面图是 (3, 1)?-可选的。 在本文中,我们将证明不含相邻 k-圈的平面图是 (3, 1)?-可选的,其中k ∈ {3, 4, 5}。

For a graph G,a list assignment is a function L that assigns a list L(v)of colors to each vertex v∈V(G).An(L,d)-coloring is a mapping?that assigns a color?(v)∈L(v)to each v∈V(G)so that at most d neighbors of v receive the color?(v).A graph G is said to be(k,d)?-choosable if it admits an(L,d)?-coloring for every list assignment L with|L(v)|≥k for all v∈V(G).Xu and Zhang conjectured that every planar graph without adjacent 3-cycles is(3,1)?-choosable.In this paper,we prove that every planar graph without adjacent k-cycles,k=3,4,5,is(3,1)?-choosable.