T-coloring


In graph theory, a T-Coloring of a graph, given the set T of nonnegative integers containing 0, is a function that maps each vertex to a positive integer such that if u and w are adjacent then. In simple words, the absolute value of the difference between two colors of adjacent vertices must not belong to fixed set T. The concept was introduced by William K. Hale. If T = it reduces to common vertex coloring.
The T-chromatic number, is the minimum number of colors that can be used in a T-coloring of G.
The complementary coloring of T-coloring c, denoted is defined for each vertex v of G by
where s is the largest color assigned to a vertex of G by the c function.

Relation to Chromatic Number

Proof. Every T-coloring of G is also a vertex coloring of G, so Suppose that and Given a common vertex k-coloring function using the colors We define as
For every two adjacent vertices u and w of G,
so Therefore d is a T-coloring of G. Since d uses k colors, Consequently,

''T''-span

The span of a T-coloring c of G is defined as
The T-span is defined as:
Some bounds of the T-span are given below: