T-coloring explained

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\N

that maps each vertex to a positive integer (color) such that if u and w are adjacent then

|c(u)-c(w)|\notinT

.^[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 = it reduces to common vertex coloring.

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)

.^[3]

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\N

using the colors

\{1,\ldots,k\}.

We define

d:V(G)\to\N

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)|\geqr+1

|d(u)-d(w)|\notinT.

Therefore d is a T-coloring of G. Since d uses k colors,

\chi_T(G)\leqk=\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|c(u)-c(w)|.

The T-span is defined as:

sp_T(G)=min_csp_T(c).

^[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)\lesp_T(G)\lesp_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)\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,

sp_T(G)\le(\chi(G)-1)t.

^[5]

Notes and References

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

T-coloring explained

Relation to chromatic number

T-span

See also

Notes and References