L(p,q)-labelling of K4-minor free graphs

For positive integers p and q, an L(p,q)-labelling of a graph G is a function φ from the vertex set V(G) to the integer set {0,1,…,k} such that |φ(x)−φ(y)|⩾p if x and y are adjacent and |φ(x)−φ(y)|⩾q if x and y are at distance 2. The L(p,q)-labelling number λ(G;p,q) of G is the smallest k such that G has an L(p,q)-labelling with max{ϕ(v)|v∈V(G)}=k.In this paper we prove that, if p+q⩾3 and G is a K4-minor free graph with maximum degree Δ, then λ(G;p,q)⩽2(2p−1)+(2q−1)⌊3Δ/2⌋−2. This generalizes a result by Lih et al. [K.W. Lih, W.F. Wang, X. Zhu, Coloring the square of a K4-minor free graph, Discrete Math. 269 (2003) 303–309], which says that every K4-minor free graph G has λ(G;1,1)⩽Δ+2 if 2⩽Δ⩽3, or λ(G;1,1)⩽⌊3Δ/2⌋ if Δ⩾4.