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

摘要

图 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}。