The adjacent vertex distinguishing total chromatic number

A well-studied concept is that of the total chromatic number. A proper total colouring of a graph is a colouring of both vertices and edges so that every pair of adjacent vertices receive different colours, every pair of adjacent edges receive different colours and every vertex and incident edge receive different colours. This paper considers a strengthening of this condition and examines the minimum number of colours required for a total colouring with the additional property that for any adjacent vertices uu and vv, the set of colours incident to uu is different from the set of colours incident to vv. It is shown that there is a constant CC so that for any graph GG, there exists such a colouring using at most Δ(G)+CΔ(G)+C colours.