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 $c:V(G)\rightarrow \mathbb {N}$ that maps each vertex of G to a positive integer (color) such that $(u,w)\in E(G)\Rightarrow \left|c(u)-c(w)\right|\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 = {0} it reduces to common vertex coloring.

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

T-chromatic number

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

Proof

Every T-coloring of G is also a vertex coloring of G, so $\chi _{T}(G)\geq \chi (G)$. Suppose that $\chi (G)=k$ and $r=max(T)$.
Given a common vertex k-coloring function $c:V(G)\rightarrow \mathbb {N}$ using the colors 1, 2,..,k. We define $d:V(G)\rightarrow \mathbb {N}$ as
$d(v)=(r+1)c(v)$
For every two adjacent vertices u and w of G,
$\left|d(u)-d(w)\right|=\left|(r+1)c(u)-(r+1)c(w)\right|$
$=(r+1)\left|c(u)-c(w)\right|\geq r+1$
so $\left|d(u)-d(w)\right|\notin T$.
Therefore d is a T-coloring of G. Since d uses k colors, $\chi _{T}(G)\leq k=\chi (G)$.
Consequently, $\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.
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$)$\leq$sp_T(G) $\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) $\leq$ ($\chi$(G)-1)(r+1). $\chi _{T}(G)=\chi (G)$.
For every graph G and every finite set T of nonnegative integers containing 0 whose cardinality is t, sp_T(G) $\leq$ ($\chi$(G)-1)t. $\chi _{T}(G)=\chi (G)$.

See also

• Graph coloring