T-coloring

In graph theory, a T-Coloring of a graph ${\displaystyle G=(V,E)}$, given the set T of nonnegative integers containing 0, is a function ${\displaystyle c:V(G)\to \mathbb{\mathbb{N}}}$ that maps each vertex to a positive integer (color) such that if u and w are adjacent then ${\displaystyle |c(u)-c(w)|\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 T-chromatic number, ${\displaystyle {\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 ${\displaystyle \bar{c}}$ is defined for each vertex v of G by

${\displaystyle \bar{c}(v)=s+1-c(v)}$

where s is the largest color assigned to a vertex of G by the c function.^[1]

Proposition. ${\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)\ge \chi (G).}$ Suppose that ${\displaystyle \chi (G)=k}$ and ${\displaystyle r=\max (T).}$ Given a common vertex k-coloring function ${\displaystyle c:V(G)\to \mathbb{\mathbb{N}}}$ using the colors ${\displaystyle \{1,\dots ,k\}.}$ We define ${\displaystyle d:V(G)\to \mathbb{\mathbb{N}}}$ as

${\displaystyle d(v)=(r+1)c(v)}$

For every two adjacent vertices u and w of G,

${\displaystyle |d(u)-d(w)|=|(r+1)c(u)-(r+1)c(w)|=(r+1)|c(u)-c(w)|\ge r+1}$

so ${\displaystyle |d(u)-d(w)|\notin T.}$ Therefore d is a T-coloring of G. Since d uses k colors, ${\displaystyle {\chi }_T(G)\le k=\chi (G).}$ Consequently, ${\displaystyle {\chi }_T(G)=\chi (G).}$

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

${\displaystyle s{p}_T(c)=\underset{u,w\in V(G)}{\max }|c(u)-c(w)|.}$

The T-span is defined as:

${\displaystyle s{p}_T(G)=\underset{c}{\min }s{p}_T(c).}$^[4]

Some bounds of the T-span are given below:

• For every k-chromatic graph G with clique of size ${\displaystyle \omega }$ and every finite set T of nonnegative integers containing 0, ${\displaystyle s{p}_T(K_{\omega })\le s{p}_T(G)\le s{p}_T(K_k).}$
• For every graph G and every finite set T of nonnegative integers containing 0 whose largest element is r, ${\displaystyle s{p}_T(G)\le (\chi (G)-1)(r+1).}$^[5]
• For every graph G and every finite set T of nonnegative integers containing 0 whose cardinality is t, ${\displaystyle s{p}_T(G)\le (\chi (G)-1)t.}$ ^[5]

• Graph coloring

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/T-coloring. Read more