Two T -colorings of a graph for T = {0, 1, 4} In graph theory , a T -Coloring
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
set T of nonnegative integers containing 0, is a function
c
:
V
(
G
)
→ → -->
N
{\displaystyle c:V(G)\to \mathbb {N} }
color ) such that if u and w are adjacent then
|
c
(
u
)
− − -->
c
(
w
)
|
∉ ∉ -->
T
{\displaystyle |c(u)-c(w)|\notin T}
[ 1] T . The concept was introduced by William K. Hale.[ 2] T = {0} it reduces to common vertex coloring.
The T -chromatic number
χ χ -->
T
(
G
)
,
{\displaystyle \chi _{T}(G),}
T -coloring of G .
The complementary coloring of T -coloring c , denoted
c
¯ ¯ -->
{\displaystyle {\overline {c}}}
v of G by
c
¯ ¯ -->
(
v
)
=
s
+
1
− − -->
c
(
v
)
{\displaystyle {\overline {c}}(v)=s+1-c(v)}
where s is the largest color assigned to a vertex of G by the c function.[ 1]
Relation to chromatic number
Proposition.
χ χ -->
T
(
G
)
=
χ χ -->
(
G
)
{\displaystyle \chi _{T}(G)=\chi (G)}
[ 3] Proof. Every T -coloring of G is also a vertex coloring of G , so
χ χ -->
T
(
G
)
≥ ≥ -->
χ χ -->
(
G
)
.
{\displaystyle \chi _{T}(G)\geq \chi (G).}
χ χ -->
(
G
)
=
k
{\displaystyle \chi (G)=k}
r
=
max
(
T
)
.
{\displaystyle r=\max(T).}
k -coloring function
c
:
V
(
G
)
→ → -->
N
{\displaystyle c:V(G)\to \mathbb {N} }
{
1
,
… … -->
,
k
}
.
{\displaystyle \{1,\ldots ,k\}.}
d
:
V
(
G
)
→ → -->
N
{\displaystyle d:V(G)\to \mathbb {N} }
d
(
v
)
=
(
r
+
1
)
c
(
v
)
{\displaystyle 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
{\displaystyle |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
)
|
∉ ∉ -->
T
.
{\displaystyle |d(u)-d(w)|\notin T.}
d is a T -coloring of G . Since d uses k colors,
χ χ -->
T
(
G
)
≤ ≤ -->
k
=
χ χ -->
(
G
)
.
{\displaystyle \chi _{T}(G)\leq k=\chi (G).}
χ χ -->
T
(
G
)
=
χ χ -->
(
G
)
.
{\displaystyle \chi _{T}(G)=\chi (G).}
T -spanThe span of a T -coloring c of G is defined as
s
p
T
(
c
)
=
max
u
,
w
∈ ∈ -->
V
(
G
)
|
c
(
u
)
− − -->
c
(
w
)
|
.
{\displaystyle sp_{T}(c)=\max _{u,w\in V(G)}|c(u)-c(w)|.}
The T -span
s
p
T
(
G
)
=
min
c
s
p
T
(
c
)
.
{\displaystyle sp_{T}(G)=\min _{c}sp_{T}(c).}
[ 4] Some bounds of the T -span are given below:
For every k -chromatic graph G with clique of size
ω ω -->
{\displaystyle \omega }
T of nonnegative integers containing 0,
s
p
T
(
K
ω ω -->
)
≤ ≤ -->
s
p
T
(
G
)
≤ ≤ -->
s
p
T
(
K
k
)
.
{\displaystyle sp_{T}(K_{\omega })\leq sp_{T}(G)\leq sp_{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
)
≤ ≤ -->
(
χ χ -->
(
G
)
− − -->
1
)
(
r
+
1
)
.
{\displaystyle sp_{T}(G)\leq (\chi (G)-1)(r+1).}
[ 5]
For every graph G and every finite set T of nonnegative integers containing 0 whose cardinality is t ,
s
p
T
(
G
)
≤ ≤ -->
(
χ χ -->
(
G
)
− − -->
1
)
t
.
{\displaystyle sp_{T}(G)\leq (\chi (G)-1)t.}
[ 5]
See also
References
^ a b 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.^ a b M. B. Cozzens and F. S. Roberts, T -colorings of graphs and the Channel Assignment Problem. Congr. Numer. 35 (1982) 191–208.
