Complexity of (p,1)-total labelling

AbstractA (p,1)-total labelling of a graph G=(V,E) is a total colouring L from V∪E into {0,…,l} such that |L(v)−L(e)|≥p whenever an edge e is incident to a vertex v. The minimum l for which G admits a (p,1)-total labelling is denoted by λp(G). The case p=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≥2. It is easy to show that λp(G)≥Δ+p−1, where Δ is the maximum degree of G. Moreover, when G is bipartite, Δ+p is an upper bound for λp(G), leaving only two possible values. In this paper, we completely settle the computational complexity of deciding whether λp(G) is equal to Δ+p−1 or to Δ+p when G is bipartite. This is trivial when Δ≤p, polynomial when Δ=3 and p=2, and NP-complete in the remaining cases