T-coloring

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)\to \mathbb {N}$ that maps each vertex to a positive integer (color) such that if u and w are adjacent then $|c(u)-c(w)|\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.

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

The T-chromatic number, $\chi _{T}(G),$ is the minimum number of colors that can be used in a T-coloring of G.

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.

Relation to chromatic number

Proposition. $\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)\to \mathbb {N}$ using the colors $\{1,\ldots ,k\}.$ We define $d:V(G)\to \mathbb {N}$ as

$d(v)=(r+1)c(v)$

For every two adjacent vertices u and w of G,

$|d(u)-d(w)|=|(r+1)c(u)-(r+1)c(w)|=(r+1)|c(u)-c(w)|\geq r+1$

so $|d(u)-d(w)|\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

The span of a T-coloring c of G is defined as

$sp_{T}(c)=\max _{u,w\in V(G)}|c(u)-c(w)|.$

The T-span is defined as:

$sp_{T}(G)=\min _{c}sp_{T}(c).$

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).$
• 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.$

See also

• Graph coloring