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]

## Contents

* 1 Relation to Chromatic Number
* 2 T-span
* 3 See also
* 4 References

## 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

1. ↑ 1.0 1.1 Chartrand, Gary; Zhang, Ping (2009). "14. Colorings, Distance, and Domination". Chromatic Graph Theory. CRC Press. pp. 397–402.
2. ↑ W. K. Hale, Frequency assignment: Theory and applications. Proc. IEEE 68 (1980) 1497–1514.
3. ↑ M. B. Cozzens and F. S. Roberts, T -colorings of graphs and the Channel Assignment Problem. Congr. Numer. 35 (1982) 191–208.
4. ↑ Chartrand, Gary; Zhang, Ping (2009). "14. Colorings, Distance, and Domination". Chromatic Graph Theory. CRC Press. p. 399.
5. ↑ 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.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/T-coloring. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=T-coloring&oldid=111740"