{{DISPLAYTITLE:''T''-coloring}} thumb|300px|Two ''T''-colorings of a graph for ''T'' = {{brace|0, 1, 4}}
In graph theory, a '''''T''-Coloring''' of a graph <math>G = (V, E)</math>, given the set ''T'' of nonnegative integers containing 0, is a function <math>c: V(G) \to \N</math> that maps each vertex to a positive integer (color) such that if ''u'' and ''w'' are adjacent then <math>|c(u) - c(w)| \notin T</math>.<ref name="garyc">{{cite book |last1=Chartrand |first1=Gary |last2=Zhang |first2=Ping|author2-link=Ping Zhang (graph theorist) |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 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.<ref>W. K. Hale, Frequency assignment: Theory and applications. Proc. IEEE 68 (1980) 1497–1514.</ref> If ''T'' = {{mset|0}} it reduces to common vertex coloring.
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 ''complementary coloring'' of ''T''-coloring ''c'', denoted <math>\overline{c}</math> is defined for each vertex ''v'' of ''G'' by : <math>\overline{c}(v) = s+1-c(v)</math> where ''s'' is the largest color assigned to a vertex of ''G'' by the ''c'' function.<ref name="garyc" />
== Relation to chromatic number ==
: '''Proposition.''' <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> Given a common vertex ''k''-coloring function <math>c: V(G) \to \N</math> using the colors <math>\{1, \ldots,k\}.</math> We define <math>d: V(G) \to \N</math> as : <math>d(v)=(r+1)c(v)</math>
For every two adjacent vertices ''u'' and ''w'' of ''G'', : <math>|d(u) - d(w)| =| (r+1)c(u) - (r+1)c(w)| =(r+1) | c(u)-c(w)| \geq r +1 </math> so <math>|d(u) - d(w)| \notin T.</math> Therefore ''d'' is a ''T''-coloring of ''G''. Since ''d'' uses ''k'' colors, <math>\chi_{T}(G)\leq k =\chi(G).</math> Consequently, <math>\chi_{T}(G)=\chi(G).</math>
== ''T''-span == The span of a ''T''-coloring ''c'' of ''G'' is defined as : <math>sp_T(c) = \max_{u,w \in V(G)} |c(u) -c(w)|.</math>
The '''''T''-span''' is defined as: : <math>sp_T(G) = \min_c sp_T(c).</math><ref name="gary">{{cite book |last1=Chartrand |first1=Gary |last2=Zhang |first2=Ping|author2-link=Ping Zhang (graph theorist) |authorlink1=Gary Chartrand |title=Chromatic Graph Theory |year=2009 |publisher=CRC Press |chapter=14. Colorings, Distance, and Domination |page=399}}</ref>
Some bounds of the ''T''-span are given below: * For every ''k''-chromatic graph ''G'' with clique of size <math>\omega</math> and every finite set ''T'' of nonnegative integers containing 0, <math>sp_T(K_{\omega}) \le sp_T(G) \le sp_T(K_k).</math> * For every graph ''G'' and every finite set ''T'' of nonnegative integers containing 0 whose largest element is ''r'', <math>sp_T(G)\le (\chi(G)-1)(r+1).</math><ref name="auto">M. B. Cozzens and F. S. Roberts, T -colorings of graphs and the Channel Assignment Problem. Congr. Numer. 35 (1982) 191–208.</ref> * For every graph ''G'' and every finite set ''T'' of nonnegative integers containing 0 whose cardinality is ''t'', <math>sp_T(G)\le (\chi(G)-1)t.</math> <ref name="auto"/>
== See also == * Graph coloring
== References == {{reflist}}
Category:Graph coloring