Graphs and Combinatorics ( Springer-Verlag 1999 T-Colorings and T-Edge Spans of Graphs*

Abstract. Suppose G is a graph and T is a set of non-negative integers that contains 0. A T-coloring of G is an assignment of a non-negative integer f \u85x to each vertex x of G such that j f \u85x ÿ f \u85yj B T whenever xy A E\u85G. The edge span of a T-coloring f is the maximum value of j f \u85x ÿ f \u85yj over all edges xy, and the T-edge span of a graph G is the minimum value of the edge span of a T-coloring of G. This paper studies the T-edge span of the d th power C dn of the n-cycle Cn for T f0; 1; 2;...; k ÿ 1g. In particular, we ®nd the exact value of the T-edge span of C dn for n1 0 or 1 (mod d 1), and lower and upper bounds for other cases. 1