不含4-圈和6-圈平面图的最优列表L(2,1)-标号

Optimal List L(2,1)-Labelling without 4-Cycles and 6-Cycles of Planar Graphs

列表L(2,1)-标号是一个重要的可以应用到信道分配问题中的优化问题,k-L(2,1)-标号是指对于一个平面图G满足映射ϕ :V (G)→{0,1,…,k},使得若d(u,v)=1,则|ϕ(u)−ϕ(v)|≥2;若d(u,v)=2,则|ϕ(u)−ϕ(v)|≥1,其中d(u,v)是图中点u和点v之间的距离。记λ(2,1)l(G)=min{k|G有一列k-L(2,1)-标号}是列表L(2,1)-标号数。在2018年,Zhu and Bu等人在全局最优化杂志中得出这样一个结论:对于不含4-圈和6-圈的平面图G有λ(2,1)l(G)≤max{Δ+15,29}。本文改进了这个结论的上界λ(2,1)l(G)≤max{Δ+12,24}。

The list L(2,1)-labelling can be applied to channel assignment problems which is an important op-timization issue. The k-L(2,1)-labelling is a mapping ϕ :V (G)→{0,1,…,k} of a graph G, such that |ϕ(u)−ϕ(v)|≥2 if d(u,v)=1 and |ϕ(u)−ϕ(v)|≥1 if d(u,v)=2, where d(u,v) is the distance between the vertex u and the vertex v in the graph. Denote λ(2,1)l(G)=min{k|G has a list k-L(2,1)-labelling} be the list L(2,1)-labelling number. In 2018, Zhu and Bu et al. demonstrated the result that λ(2,1)l(G)≤max{Δ+15,29} for the planar graph G with-out 4-cycles and 6-cycles. In this paper we improve the upper bound of this result to λ(2,1)l(G)≤max{Δ+12,24}.