不含相邻短圈的平面图的 (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}。

Abstract: 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.