T-coloring

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

In graph theory, a T-Coloring of a graph [math]\displaystyle{ G = (V, E) }[/math], given the set T of nonnegative integers containing 0, is a function [math]\displaystyle{ c: V(G) \to \N }[/math] that maps each vertex to a positive integer (color) such that if u and w are adjacent then [math]\displaystyle{ |c(u) - c(w)| \notin T }[/math].^[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, [math]\displaystyle{ \chi_{T}(G), }[/math] is the minimum number of colors that can be used in a T-coloring of G.

The complementary coloring of T-coloring c, denoted [math]\displaystyle{ \overline{c} }[/math] is defined for each vertex v of G by

[math]\displaystyle{ \overline{c}(v) = s+1-c(v) }[/math]

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

Relation to Chromatic Number

Proposition. [math]\displaystyle{ \chi_{T}(G)=\chi(G) }[/math].^[3]

Proof. Every T-coloring of G is also a vertex coloring of G, so [math]\displaystyle{ \chi_{T}(G)\geq \chi(G). }[/math] Suppose that [math]\displaystyle{ \chi(G)=k }[/math] and [math]\displaystyle{ r=\max(T). }[/math] Given a common vertex k-coloring function [math]\displaystyle{ c: V(G) \to \N }[/math] using the colors [math]\displaystyle{ \{1, \ldots,k\}. }[/math] We define [math]\displaystyle{ d: V(G) \to \N }[/math] as

[math]\displaystyle{ d(v)=(r+1)c(v) }[/math]

For every two adjacent vertices u and w of G,

[math]\displaystyle{ |d(u) - d(w)| =| (r+1)c(u) - (r+1)c(w)| =(r+1) | c(u)-c(w)| \geq r +1 }[/math]

so [math]\displaystyle{ |d(u) - d(w)| \notin T. }[/math] Therefore d is a T-coloring of G. Since d uses k colors, [math]\displaystyle{ \chi_{T}(G)\leq k =\chi(G). }[/math] Consequently, [math]\displaystyle{ \chi_{T}(G)=\chi(G). }[/math]

T-span

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

[math]\displaystyle{ sp_T(c) = \max_{u,w \in V(G)} |c(u) -c(w)|. }[/math]

The T-span is defined as:

[math]\displaystyle{ sp_T(G) = \min_c sp_T(c). }[/math]^[4]

Some bounds of the T-span are given below:

• For every k-chromatic graph G with clique of size [math]\displaystyle{ \omega }[/math] and every finite set T of nonnegative integers containing 0, [math]\displaystyle{ sp_T(K_{\omega}) \le sp_T(G) \le sp_T(K_k). }[/math]

• For every graph G and every finite set T of nonnegative integers containing 0 whose largest element is r, [math]\displaystyle{ sp_T(G)\le (\chi(G)-1)(r+1). }[/math]^[5]

• For every graph G and every finite set T of nonnegative integers containing 0 whose cardinality is t, [math]\displaystyle{ sp_T(G)\le (\chi(G)-1)t. }[/math] ^[5]

See also

• Graph coloring

References

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