The complexity of the L(p,q)L(p,q)-labeling problem for bipartite planar graphs of small degree

Given a simple graph GG, by an L(p,q)L(p,q)-labeling of GG we mean a function cc that assigns nonnegative integers to its vertices in such a way that if two vertices uu, vv are adjacent then |c(u)−c(v)|≥p|c(u)−c(v)|≥p, and if they are at distance 2 then |c(u)−c(v)|≥q|c(u)−c(v)|≥q. The L(p,q)L(p,q)-labeling problem can be defined as follows: given a graph GG and integer tt, determine whether there exists an L(p,q)L(p,q)-labeling cc of GG such that c(V)⊆{0,1,…,t}c(V)⊆{0,1,…,t}. In the paper we show that the problem is NPNP-complete even when restricted to bipartite planar graphs of small maximum degree and for relatively small values of tt. More precisely, we prove that: (1)if p<3qp<3q then the problem is NPNP-complete for bipartite planar graphs of maximum degree Δ≤3Δ≤3 and t=p+max{2q,p}t=p+max{2q,p};(2)if p=3qp=3q then the problem is NPNP-complete for bipartite planar graphs of maximum degree Δ≤4Δ≤4 and t=6qt=6q;(3)if p>3qp>3q then the problem is NPNP-complete for bipartite planar graphs of maximum degree Δ≤4Δ≤4 and t=p+5qt=p+5q.In particular, these results imply that the L(2,1)L(2,1)-labeling problem in planar graphs is NPNP-complete for t=4t=4, and that the L(p,q)L(p,q)-labeling problem in graphs of maximum degree Δ≤4Δ≤4 is NPNP-complete for all values of pp and qq, thus answering two well-known open questions.