On the L(p,1)L(p,1)-labelling of graphs

The L(p,q)L(p,q)-labelling of graphs, is a graph theoretic framework introduced by Griggs and Yeh [Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586–595] to model the channel assignment problem  . In this paper we improve the best known upper bound for the L(p,1)L(p,1)-labelling of graphs with given maximum degree. We show that for any integer p⩾2p⩾2, any graph G   with maximum degree ΔΔ admits an L(p,1)L(p,1)-labelling such that the labels range from 0 to Δ2+(p-1)Δ-2Δ2+(p-1)Δ-2.