dd-strong total colorings of graphs

For a proper total coloring of a graph G=(V,E)G=(V,E) the palette C(v)C(v) of a vertex v∈Vv∈V is the set of the colors of the incident edges and the color of the vertex itself. If C(u)≠C(v)C(u)≠C(v) then the two vertices uu and vv of GG are distinguished by the total coloring. A dd-strong total coloring of GG is a proper total coloring that distinguishes all pairs of vertices uu and vv with distance 1≤d(u,v)≤d1≤d(u,v)≤d. The dd-strong total chromatic number χd″(G) of GG is the minimum number of colors of a dd-strong total coloring of GG. Such total colorings generalize strong total colorings and adjacent strong total colorings as well.In this paper we present general lower bounds, determine χd″(G) completely for paths and give exact values and bounds for cycles and for circulant graphs. Moreover, we disprove a conjecture on a general upper bound for χd″(G) (Zhang et al., 2006).