T-coloring

Two T-colorings of a graph for T = Template:Brace

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)->ℕ that maps each vertex to a positive integer (color) such that if u and w are adjacent then |c(u)−c(w)|∉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, χ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 c‾ is defined for each vertex v of G by

c‾(v)=s+1−c(v)

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. χT(G)=χ(G).[3]

Proof. Every T-coloring of G is also a vertex coloring of G, so χT(G)≥χ(G). Suppose that χ(G)=k and r=max⁡(T). Given a common vertex k-coloring function c:V(G)->ℕ using the colors {1,…,k}. We define d:V(G)->ℕ as

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)|≥r+1

so |d(u)−d(w)|∉T. Therefore d is a T-coloring of G. Since d uses k colors, χT(G)≤k=χ(G). Consequently, χT(G)=χ(G).

## T-span

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

spT(c)=maxu,w∈V(G)|c(u)−c(w)|.

The T-span is defined as:

spT(G)=mincspT(c).[4]

Some bounds of the T-span are given below:

* For every k-chromatic graph G with clique of size ω and every finite set T of nonnegative integers containing 0, spT(Kω)≤spT(G)≤spT(Kk).
* For every graph G and every finite set T of nonnegative integers containing 0 whose largest element is r, spT(G)≤(χ(G)−1)(r+1).[5]
* For every graph G and every finite set T of nonnegative integers containing 0 whose cardinality is t, spT(G)≤(χ(G)−1)t. [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=4229552"