LABELING CHORDAL GRAPHS - DISTANCE 2 CONDITION

An L(2, 1)-labeling of a graph G is an assignment of nonnegative integ ers to the vertices of G such that adjacent vertices get numbers at le ast two apart, and vertices at distance two get distinct numbers. The L(2, l)-labeling number of G, lambda(G), is the minimum range of label s over all such labelings. It is shown that, for chordal graphs G with maximum degree Delta(G), lambda(G) less than or equal to (Delta(G) 3)(2)/4; in particular, if G is a unit interval graph with chromatic n umber (X)(G), lambda(G) less than or equal to 2(X)(G), which is a bett er bound. As a consequence, it is shown that the conjecture lambda(G) less than or equal to Delta(2)(G) by Griggs and Yeh [SIAM J.Discrete M ath., 5 (1992), pp. 586-595] is true for chordal graphs.