Griggs and Yeh's Conjecture and $L(p,1)$-labelings

Abstract

An $L(p,1)$-labeling of a graph is a function f from the vertex set to the positive integers such that $|f(x)-f(y)|\geqslant p$ if dist$(x,y)=1$ and $|f(x)-f(y)|\geqslant 1$ if dist$(x,y)=2$, where dist$(x,y)$ is the distance between the two vertices x and y in the graph. The span of an $L(p,1)$-labeling f is the difference between the largest and the smallest labels used by f. In 1992, Griggs and Yeh conjectured that every graph with maximum degree $\Delta\geqslant 2$ has an $L(2,1)$-labeling with span at most $\Delta^2$. We settle this conjecture for $\Delta$ sufficiently large. More generally, we show that for any positive integer p there exists a constant $\Delta_p$ such that every graph with maximum degree $\Delta\geqslant \Delta_p$ has an $L(p,1)$-labeling with span at most $\Delta^2$. This yields that for each positive integer p, there is an integer $C_p$ such that every graph with maximum degree $\Delta$ has an $L(p,1)$-labeling with span at most $\Delta^2+C_p$.