[r, s, t]-Colorings of graphs

Given non-negative integers r, s, and t, an [r, s, t]-coloring of a graph G = (V(G), E(G)) is a mapping c from V(G) U E(G) to the color set {0, 1,..., k - 1} such that vertical bar c(v(i)) - c(v(j))vertical bar >= r for every two adjacent vertices v(i), v(j), vertical bar c(e(i)) - c(e(j))vertical bar >= s for every two adjacent edges e(i), e(j), and vertical bar c(v(i)) - c(e(j))vertical bar >= t for all pairs of incident vertices and edges, respectively. The [r, s, t]-chromatic number X,,t (G) of G is defined to be the minimum k such that G admits an [r, s, t]-coloring. This is an obvious generalization of all classical graph colorings since c is a vertex coloring if r = 1, s = t = 0, an edge coloring if s = 1, r = t = 0, and a total coloring if r = s = t = 1, respectively. We present first results on chi(r.s,t)(G) such as general bounds and also exact values, for example if min{r, s, t] = 0 or if G is a complete graph. (c) 2006 Elsevier B.V. All rights reserved.