T-coloring

Two T -colorings of a graph for T = {0, 1, 4}

In graph theory, a T-Coloring of a graph $G=(V,E)$, given the set T of nonnegative integers containing 0, is a function ${\displaystyle c:V(G)\rightarrow \mathbb {N} }$ that maps each vertex of G to a positive integer (color) such that ${\displaystyle (u,w)\in E(G)\Rightarrow \left|c(u)-c(w)\right|\notin T}$.^[1] 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.^[2] If T = {0} it reduces to common vertex coloring.

The complementary coloring of T-coloring c, denoted ${\displaystyle {\overline {c}}}$ is defined for each vertex v of G by
${\displaystyle {\overline {c}}(v)=s+1-c(v)}$
where s is the largest color assigned to a vertex of G by the c function.^[1]

T-chromatic number

The T-chromatic number ${\displaystyle \chi _{T}(G)}$ 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. ${\displaystyle \chi _{T}(G)=\chi (G)}$.^[3]

Proof

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

T-span

For a T-coloring c of G, the c-span sp_T(c) = max {|c(u)-c(w)|} over all uw $\in$ V(G).
The T-span sp_T(G) of G is min {sp_T(c)} of all colourings c of G. ^[4]
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_$\omega$)${\displaystyle \leq }$sp_T(G) ${\displaystyle \leq }$ 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) ${\displaystyle \leq }$ ($\chi$(G)-1)(r+1). ${\displaystyle \chi _{T}(G)=\chi (G)}$.^[5]
For every graph G and every finite set T of nonnegative integers containing 0 whose cardinality is t, sp_T(G) ${\displaystyle \leq }$ ($\chi$(G)-1)t. ${\displaystyle \chi _{T}(G)=\chi (G)}$.^[5]

See also

• Graph coloring

References

1. Chartrand, Gary; Zhang, Ping (2009). "14. Colorings, Distance, and Domination". Chromatic Graph Theory. CRC Press. pp. 397–402.
2. W. K. Hale, Frequency assignment: Theory and applications. Proc. IEEE 68 (1980) 1497-1514.
3. M. B. Cozzens and F. S. Roberts, T -colorings of graphs and the Channel Assignment Problem. Congr. Numer. 35 (1982) 191-208.
4. Chartrand, Gary; Zhang, Ping (2009). "14. Colorings, Distance, and Domination". Chromatic Graph Theory. CRC Press. p. 399.
5. M. B. Cozzens and F. S. Roberts, T -colorings of graphs and the Channel Assignment Problem. Congr. Numer. 35 (1982) 191-208.