Labeling Chordal Graphs: Distance Two Condition

Abstract

An $L( 2,1 )$-labeling of a graph G is an assignment of nonnegative integers to the vertices of G such that adjacent vertices get numbers at least two apart, and vertices at distance two get distinct numbers. The $L( 2,1 )$-labeling number of $G,\lambda ( G )$, is the minimum range of labels over all such labelings. It is shown that, for chordal graphs G with maximum degree $\Delta ( G ),\lambda ( G ) \leq ( \Delta ( G ) + 3 )^2 /4$; in particular, if G is a unit interval graph with chromatic number $\chi ( G ),\lambda ( G ) \leq 2\chi ( G )$, which is a better bound. As a consequence, it is shown that the conjecture $\lambda ( G ) \leq \Delta^2 ( G )$ by Griggs and Yeh [SIAM J. Discrete Math., 5 (1992), pp. 586–595] is true for chordal graphs.