Complexity of (p,1)(p,1)-total labelling

A (p,1)(p,1)-total labelling   of a graph G=(V,E)G=(V,E) is a total colouring LL from V∪EV∪E into {0,…,l}{0,…,l} such that |L(v)−L(e)|≥p|L(v)−L(e)|≥p whenever an edge ee is incident to a vertex vv. The minimum ll for which GG admits a (p,1)(p,1)-total labelling is denoted by λp(G)λp(G). The case p=1p=1 corresponds to the usual notion of total colouring, which is NP-hard to compute even for cubic bipartite graphs [C.J. McDiarmid, A. Sánchez-Arroyo, Total colouring regular bipartite graphs is NP-hard, Discrete Math. 124 (1994), 155–162]. In this paper we assume p≥2p≥2. It is easy to show that λp(G)≥Δ+p−1λp(G)≥Δ+p−1, where ΔΔ is the maximum degree of GG. Moreover, when GG is bipartite, Δ+pΔ+p is an upper bound for λp(G)λp(G), leaving only two possible values. In this paper, we completely settle the computational complexity of deciding whether λp(G)λp(G) is equal to Δ+p−1Δ+p−1 or to Δ+pΔ+p when GG is bipartite. This is trivial when Δ≤pΔ≤p, polynomial when Δ=3Δ=3 and p=2p=2, and NP-complete in the remaining cases.