Finite-dimensional T-colorings of graphs
This article proposes finite-dimensional T-colorings on simple graphs. The ordinary T-coloring will be the one-dimensional version of our T-colorings. Let at be a positive integer and T be a set of nonnegative integers that contains 0. Denote Z(0)(d) = {(x(1),x(2),...,x(d)):x(i) is an element of Z(0), 1 less than or equal to i less than or equal to d}, where Z(0) = {0,1,2,...}. A d-dimensional infinite-norm, parallel to (.)parallel to (infinity), is a function from Z(0)(d) to Z(0) that parallel toX parallel to (infinity) = max {\x(t)\ : 1 less than or equal to i less than or equal to d} for X = (x(1),x(2),...,x(d)). A d-dimensional one-norm, parallel to (.)parallel to (1), is a function from Z(0)(d) to Z(0) that parallel toX parallel to (1) = Sigma (d)(i=1) \x(i)\ for X = (x(1),x(2),...x(d)) in Z(0)(d). With these norms, we define a d-dimensional T-coloring with respect to p-norm (p = 1 or infinity), f, on a graph G = (V,E) as follows: f:V --> Z(0)(d) such that parallel tof(u) - f(v)parallel top is not an element of T, for all {u,v} is an element of E. They are denoted by T(d,p)-colorings. Note that both T-colorings for d = I are same as usual T-colorings. The edge span of a T(d, p)-coloring f on a graph G, esp(T)(f; d, p), is the maximum value of {parallel tof(u) - f(v)parallel to (p) : {u,v} is an element of E(G)}. The edge span of G with respect to T(d, p)-coloring is the smallest number m such that there is a T(d,p) coloring f with esp(T)(f;d,p) = m. it is denoted by esp(T)(G; d, p). We will show that the edge spans of complete graphs play important roles in seeking edge spans on general graphs. Ns, the goal of this paper is concentrated in finding edge spans of complete graphs. This is same as in the usual T-coloring problem. (C) 2001 Published by Elsevier Science B.V.
t-coloring norm distance graph graph homomorphism