r, s, t-COLORINGS OF STARS

摘要

Given non-negative integers r, s, and t, an [r, s, t]-coloring of a graph G with vertex set V(G) and edge set E (G) is a mapping c from V(G)UE(G) to the color set {0,1,... ,k- 1} such that |c(v_i)-c(v_i)| ≥ r every two adjacent vertices v_i,v_j, |c(e_i) - c(e_j)| ≥ s for any two adjacent edges e_i,e_j, and |c(v_i) - c(e_j)| ≥ t for all pairs of incident vertices and edges, respectively. The [r, s, t]-chromatic number χr,s,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 = i = 0, and a total coloring if r = s = t = l, respectively. In this paper, we completely determine the [r, s, t]-chromatic numbers for stars. Thus we obtain a lower bound for χr,s,t(G) for an arbitrary graph G that only depends on r, s, t and the maximum degree Δ(G).