Δ(G)=3的图的列表-L(2,1)-标号

The list-L(2,1)-labeling of graph with Δ(G)=3

记Δ(G)和λl(G)分别为图G的最大度和列表-L(2,1)-标号数.若Δ(G)≤3,则称G为子三次图.证明了若G是子三次图,那么λl(G)≤12;若G为最大平均度Mad(G)<8/3的子三次图,那么λl(G)≤10.这一结果进一步支撑了Griggs和Yeh关于距离2标号的猜想.

For a graph G, let AG andλl（G） denote the maximum degree and the list-L（2,1）-labeling number of G, respectively. If △（G）≤3, then we say G is subcubic. In this paper, we show that if G is a subcubic graph, thenλl（G）≤12. In addition, we show that if G is a subcubic graph with maximum average degree Mad（G）〈8/3, then λl （G）≤10. These results further support Griggs and Yeh＇s conjecture.