T-coloring

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 ℕ$ that maps each vertex to a positive integer (color) such that if u and w are adjacent then $| c (u) - c (w) | \notin T$ . 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. 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 $\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.

χ_{T} (G) = χ (G)

.

Proof. Every T-coloring of G is also a vertex coloring of G, so $χ_{T} (G) \geq χ (G) .$ Suppose that $χ (G) = k$ and $r = max (T) .$ Given a common vertex k-coloring function $c : V (G) \to ℕ$ using the colors ${1, \dots, k} .$ We define $d : V (G) \to ℕ$ 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) | \geq r + 1

so $| d (u) - d (w) | \notin T .$ Therefore d is a T-coloring of G. Since d uses k colors, $χ_{T} (G) \leq k = χ (G) .$ Consequently, $χ_{T} (G) = χ (G) .$

T-span

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

s p_{T} (c) = max_{u, w \in V (G)} | c (u) - c (w) | .

The T-span is defined as:

s p_{T} (G) = min_{c} s p_{T} (c) .

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, $s p_{T} (K_{ω}) \leq s p_{T} (G) \leq s p_{T} (K_{k}) .$
For every graph G and every finite set T of nonnegative integers containing 0 whose largest element is r, $s p_{T} (G) \leq (χ (G) - 1) (r + 1) .$
For every graph G and every finite set T of nonnegative integers containing 0 whose cardinality is t, $s p_{T} (G) \leq (χ (G) - 1) t .$

References

1 2 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.
1 2 M. B. Cozzens and F. S. Roberts, T -colorings of graphs and the Channel Assignment Problem. Congr. Numer. 35 (1982) 191–208.

[garyc-1] 1 2 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.

[gary-4] Chartrand, Gary; Zhang, Ping (2009). "14. Colorings, Distance, and Domination". Chromatic Graph Theory. CRC Press. p. 399.

[auto-5] 1 2 M. B. Cozzens and F. S. Roberts, T -colorings of graphs and the Channel Assignment Problem. Congr. Numer. 35 (1982) 191–208.

T-coloring

Relation to chromatic number

T-span

See also

References