T-coloring

In graph theory, a T-Coloring of a graph $G = (V, E)$, given the set ''T'' of nonnegative integers containing 0, is a function $c: V(G) \to \N$ that maps each vertex to a positive integer (color) such that if ''u'' and ''w'' are adjacent then $, c(u) - c(w), \notin T$. 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, $\chi_(G),$ is the minimum number of colors that can be used in a ''T''-coloring of ''G''.

The ''complementary coloring'' of ''T''-coloring ''c'', denoted $\overline$ is defined for each vertex ''v'' of ''G'' by

:$\overline(v) = s+1-c(v)$

where ''s'' is the largest color assigned to a vertex of ''G'' by the ''c'' function.

Relation to Chromatic Number

:Proposition. $\chi_(G)=\chi(G)$.M. B. Cozzens and F. S. Roberts, T -colorings of graphs and the Channel Assignment Problem. Congr. Numer. 35 (1982) 191–208.

Proof. Every ''T''-coloring of ''G'' is also a vertex coloring of ''G'', so $\chi_(G)\geq \chi(G).$ Suppose that $\chi(G)=k$ and $r=\max(T).$ Given a common vertex ''k''-coloring function $c: V(G) \to \N$ using the colors $\.$ We define $d: V(G) \to \N$ as

:$d(v)=(r+1)c(v)$

For every two adjacent vertices ''u'' and ''w'' of ''G'',

:$, d(u) - d(w), =, (r+1)c(u) - (r+1)c(w), =(r+1) , c(u)-c(w), \geq r +1$

so $, d(u) - d(w), \notin T.$ Therefore ''d'' is a ''T''-coloring of ''G''. Since ''d'' uses ''k'' colors, $\chi_(G)\leq k =\chi(G).$ Consequently, $\chi_(G)=\chi(G).$

''T''-span

The span of a ''T''-coloring ''c'' of ''G'' is defined as

:$sp_T(c) = \max_ , c(u) -c(w), .$

The ''T''-span is defined as:

:$sp_T(G) = \min_c sp_T(c).$

Some bounds of the ''T''-span are given below:

* For every ''k''-chromatic graph ''G'' with clique of size $\omega$ and every finite set ''T'' of nonnegative integers containing 0, $sp_T(K_) \le sp_T(G) \le sp_T(K_k).$

*For every graph ''G'' and every finite set ''T'' of nonnegative integers containing 0 whose largest element is ''r'', $sp_T(G)\le (\chi(G)-1)(r+1).$M. B. Cozzens and F. S. Roberts, T -colorings of graphs and the Channel Assignment Problem. Congr. Numer. 35 (1982) 191–208.

*For every graph ''G'' and every finite set ''T'' of nonnegative integers containing 0 whose cardinality is ''t'', $sp_T(G)\le (\chi(G)-1)t.$

See also

*Graph coloring

References

{{reflist

Graph coloring