View source for Linoleate 10R-lipoxygenase

[[File:T-colorings.png|thumb|300px|Two T -colorings of a graph for T = {0, 1, 4}]]In [[graph theory]], a '''T-Coloring''' of a graph <math>G = (V, E)</math>, given the [[Set (mathematics)|set]] ''T'' of nonnegative integers containing 0, is a function <math>c: V(G) \rightarrow \mathbb{N}</math> of [[Graph coloring|colors]] (positive integers) to the vertices of ''G'' such that if <math>(u,w) \in E(G) \Rightarrow  \left | c(u) - c(w) \right | \notin T</math>.<ref name="gary">{{cite book |last1=Chartrand |first1=Gary |last2=Zhang |first2=Ping |authorlink1=Gary Chartrand |title=Chromatic Graph Theory |year=2009 |publisher=CRC Press |chapter=14. Colorings, Distance, and Domination |pages=397-402}}</ref> In simple words, the distance between two colors of adjacent vertices must not belong to fixed set ''T''. The concept was introduced by William K. Hale.<ref>W. K. Hale, Frequency assignment: Theory and applications. Proc. IEEE 68 (1980) 1497-1514.</ref> If ''T = {0}'' it reduces to common vertex coloring.

The ''complementary coloring'' of ''T''-coloring ''c'', denoted <math>\overline{c}</math> is defined for each vertex ''v'' of ''G'' by
<br><math>\overline{c}(v) = s +1-c(v)</math><br>
where ''s'' is the largest color assigned to a vertex of ''G'' by the ''c'' function.<ref name="gary" />

== ''T''-chromatic number ==
The ''T-chromatic number'' <math>\chi_{T}(G)</math> is the minimum number of colors that can be used in a ''T''-coloring of ''G''.  The ''T''-chromatic number is equal to the chromatic number. <math>\chi_{T}(G)=\chi(G)</math>.<ref>M. B. Cozzens and F. S. Roberts, T -colorings of graphs and the Channel
Assignment Problem. Congr. Numer. 35 (1982) 191-208.</ref>

=== Proof ===
Every ''T''-coloring of ''G'' is also a vertex coloring of ''G'', so <math>\chi_{T}(G)\geq \chi(G)</math>. Suppose that <math>\chi(G)=k</math> and <math>r=max(T)</math>.<br>
Given a common vertex k-coloring function <math>c: V(G) \rightarrow \mathbb{N}</math> using the colors 1, 2,..,k. We define <math>d: V(G) \rightarrow \mathbb{N}</math> as
<br><math>d(v)=(r+1)c(v)</math><br>
For every two adjacent vertices u and w of G,
<br><math>\left | d(u) - d(w) \right |  = \left | (r+1)c(u) - (r+1)c(w) \right |</math><br>
<math>=(r+1)\left | c(u)-c(w) \right | \geq r +1 </math><br>
so <math>\left | d(u) - d(w) \right |  \notin T</math>.<br>Therefore ''d'' is a ''T''-coloring of ''G''. Since ''d'' uses ''k'' colors, <math>\chi_{T}(G)\leq k =\chi(G)</math>.<br>
Consequently, <math>\chi_{T}(G)=\chi(G)</math> {{Unicode|■}}

== See also ==
*[[Graph coloring]]

== References ==
{{reflist}}

[[Category:Graph coloring]]