关于图的L(3,2,1)-标号问题

图G的L( 2 ,1 )标号是一个从顶点集V(G)到非负整数集的函数f(x) .使得若d(x ,y) =1 .则｜f(x) -f(y) ｜≥ 2 ;若d(x ,y) =2 ,则｜f(x) -f(y)｜≥ 1 .图G的L( 2 ,1 )标号数λ(G)是使得G有max{f(v) ∶v∈V(G) }=k的L( 2 ,1 )标号中的最小数k .本文将L( 2 ,1 ) 标号问题推广到更一般的情形即L( 3,2 ,1 ) 标号问题 .我们首先定义了图G的顶点 3 着色及图的 3 色数 χ3 (G)等有关概念 ,并推导出 3 色数 χ3 (G)的上界 ;然后根据 χ3 (G)与λ3 (G)的关系 ,得出了对一般图G ,有λ3 (G) ≤ 3maxH Gδ(H) (Δ2 -Δ 1 )这一一般关系式 ;最后证明了对一般平面图G ,有λ3 (G)≤ 1 5(Δ2 -Δ 1 ) ,并得出了其它几类平面图的λ3 (G)的上界 .

The L(3,2,1)- Labeling Problem on Graphs

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 ( mzxδ H( )G (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.