Supriya Ghosh (Editor)

T coloring

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
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 ) → N that maps each vertex of G to a positive integer (color) such that ( u , w ) ∈ E ( G ) ⇒ | c ( u ) − c ( w ) | ∉ 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.

Contents

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.

T-chromatic number

The T-chromatic number χ T ( G ) is the minimum number of colors that can be used in a T-coloring of G. The T-chromatic number is equal to the chromatic number. χ T ( G ) = χ ( G ) .

Proof

Every T-coloring of G is also a vertex coloring of G, so χ T ( G ) ≥ χ ( G ) . Suppose that χ ( G ) = k and r = m a x ( T ) .
Given a common vertex k-coloring function c : V ( G ) → N using the colors 1, 2,..,k. We define d : V ( G ) → N 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

For a T-coloring c of G, the c-span spT(c) = max {|c(u)-c(w)|} over all uw ∈ V(G).
The T-span spT(G) of G is min {spT(c)} of all colourings c of G.
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). χ T ( G ) = χ ( G ) .
For every graph G and every finite set T of nonnegative integers containing 0 whose cardinality is t, spT(G) ≤ ( χ (G)-1)t. χ T ( G ) = χ ( G ) .

References

T-coloring Wikipedia
(Text) CC BY-SA