T-coloring

File:T-colorings.png

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