The L(3,2,1)-Labeling Problem on Graphs
Liu Jia-zhuang · Mathematica Applicata · 2004
An L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)-f(y)|≥2 if d(x,y)=1 and |f(x)-f(y)|≥1 if d(x,y)=2.The L(2,1)-labeling number λ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v)∶v∈V(G)}=k.We generalize the L(2,1)-labeling to the L(3,2,1)-labeling in this paper.We firstly define vertex 3-coloring,3-chromatic number χ 3(G) and other related concepts,and give the upper bound of 3-chromatic number χ 3(G);we then derive λ 3(G)≤3 maxHGδ(H)(Δ2-Δ+1) for any graph G with maximum degree Δ;finally,we prove that λ 3(G)≤15(Δ2-Δ+1) for any planar graph G with maximum degree Δ,and give upper bounds of λ 3(G) of several other graphs.