An Algorithm To Compute The T-Colorings Of Multigraphs

T-colorings of graphs arose from the frequency assignment problem. Hale[8] formulated it in graph theory language. T is the interference set. That is , if we want to assign frequencies to a pair of adjacent cities or radio stations, then the difference of those two frequencies used has to avoid the set T.The T-colorings of multigraphs is a more practical case of T-colorings of graphs where interference may occur on different level. A multi-graph G can be partitioned into K distinct sets, so we represent G as G(V, G0, G1, G2,..., GK-1). A T-coloring of G(V, G0, g1, G2,.., GK-1) is a function f satisfying that it is simultaneously a T(i)-coloring of Gi for all i, i.e., so that for i = 0,1,... ,K - 1, {x,y} ∈E (Gi) |f(x) - f(y)| (?) T(i). The order of a T-coloring f of G is the number of distinct values of /(x), x ∈ V(G). The span of a T-coloring f of G equals max |f(x)- f(y)|, where the maximum is taken over all vertex in V(G). The minimum order, and minimum span, where the minimum is taken over all T-colorings of G, are denoted by xT(G), and spT(G), respectively.We will show several previous results of the span of simple graphs and multigraphs, and we also will present a new algorithm to compute spT of multigraphs, furthermore we will discuss the bound of the span of a special multigraph and the algorithm of spT(Kn).