T-coloring
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
References
- ↑ 1.0 1.1 Chartrand, Gary; Zhang, Ping (2009). "14. Colorings, Distance, and Domination". Chromatic Graph Theory. CRC Press. pp. 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.
- ↑ Chartrand, Gary; Zhang, Ping (2009). "14. Colorings, Distance, and Domination". Chromatic Graph Theory. CRC Press. p. 399.
- ↑ 5.0 5.1 M. B. Cozzens and F. S. Roberts, T -colorings of graphs and the Channel Assignment Problem. Congr. Numer. 35 (1982) 191–208.
 |  |
