高度平面图的列表L(p,q)-标号

The List L(p,q)-labelings of Planar Graphs with High Maximum Degree

如果平面图G的最大度Δ(G)=V|(G)|-k,k=1,2,…,则称G为一个hk-图,k=1,2的hk-图称为高度平面图.研究了高度平面图G的列表L(p,q)-标号问题,给出了高度平面图G的列表L(p,q)-标号数λl(G;p,q)的上界,并对h1-图证明了λl(G;p,q)≤(2q-1)Δ+6(p-q);对h2-图有λl(G;p,q)≤(2q-1)Δ+8p-6q-1.

Let G be a planar graph, for k = 1,2,…, we call G an hk-graph, if △（G） = ｜V（ G） ｜ -k. In this paper, we studied the upper bound of λl（G;p,q） on planar graphs with high maximum degree, and prove that λl（G;p,q） ≤（2q- 1）△ ＋6（p-q） for ht-graph and λl（G;p,q） ≤（2q- 1）（G） △＋8p-6q- 1 for h2-graph.