# General Vertex-Distinguishing Total Coloring of Graphs

Authors: Chanjuan Liu; Enqiang Zhu
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The general vertex-distinguishing total chromatic number of a graphG is the minimum integer k, for which the vertices and edges of G are colored using k colors such that any two vertices have distinct sets of colors of them and their incident edges. In this paper, we figure out the exact value of this chromatic number of some special graphs and propose a conjecture on the upper bound of this chromatic number.


---

## Body

## 1. Introduction

All graphs considered in this paper are simple and finite. For a graphG, we denote by V
(
G
), E
(
G
), Δ
(
G
), and δ
(
G
) the sets of vertices, edges, maximum degree, and minimum degree of G, respectively. For a vertex v of G, d
G
(
v
) is the degree of v in G. For any V
′
⊆
V
(
G
), we use G
[
V
′
] to denote the subgraph induced by V
′. For any undefined terms, the reader is referred to the book [1].The coloring problem of graphs is one of the classical research areas in graph theory. It has been widely applied to various fields, such as large scheduling [2], assignment of radio frequency [3], and separating combustible chemical combinations [4]. Due to its extensive application, many new variants of colorings have been studied [5].Recall that ak
-edge coloring of a graph G is a mapping f: E
(
G
)
→
C, where C is a set of k colors. An edge coloring isproper if adjacent edges receive distinct colors. In 1985, Harary and Plantholt [6] first considered point-distinguishing chromatic index, which is a variant of edge coloring. After that, many other variants of edge coloring were introduced, such as vertex-distinguishing proper edge coloring [7], adjacent vertex-distinguishing edge coloring [8], and general adjacent vertex-distinguishing edge coloring [9].A totalk-coloring of a graph G is a coloring of V
(
G
)
∪
E
(
G
) using k colors. A total k-coloring isproper if no two adjacent or incident elements receive the same color. The minimum number of colors required for a proper total coloring of G is called the total chromatic number of G and is denoted by χ
t
(
G
). Behzad [10] and Vizing [11] independently made the conjecture that, for any graph G,
(1)
χ
t
(
G
)
≤
(
G
)
+
2
.
This is known as the total coloring conjecture (T
C
C) and is still unproven.Letf be a total k-coloring of G. Thetotal color set (with respect to f) of a vertex v
∈
V
(
G
) is the set, denoted by C
f
(
v
), of colors of v and its incident edges. We denote by C
f
(
G
) the set of total color sets of all vertices of G. Furthermore, let S be a subset of V
(
G
)
∪
E
(
G
); we use C
f
(
S
) to denote the set of colors of elements of S.Like edge coloring, total coloring also has some variants. In 2005, Zhang et al. [12] added a restriction to the definition of total coloring and proposed a new type of coloring defined as follows.Definition 1.
Letf be a proper total k-coloring of a graph G. If, for all u
,
v
∈
V
(
G
), C
f
(
u
)
≠
C
f
(
v
), then f is called an adjacent vertex-distinguishing total k-coloring of G, or a k
-AVDTC of G for short. The minimum number k for which G has a k
-AVDTC is the adjacent vertex-distinguishing total chromatic number of G, denoted by χ
a
t
(
G
).Zhang et al. [12] conjectured that, for any graph G, it has
(2)
χ
a
t
(
G
)
≤
Δ
(
G
)
+
3
.
In [13–15], authors proved that there exists a 6-AVDTC of graphs with Δ
=
3, which indicates conjecture (2) holds for such graphs. For further research on adjacent vertex-distinguishing total chromatic number, one may refer to [16–23].For ak-AVDTC
f of a graph G, if C
f
(
u
)
≠
C
f
(
v
) is required for any two distinct vertices u
,
v, then f is called avertex-distinguishing total
k
-coloring of G, abbreviated as k
-VDTC. The minimum number k such that G has a k
-VDTC is called the vertex-distinguishing total chromatic number, denoted by χ
v
t
(
G
) [24]. Zhang et al. conjectured in [24] that, for any graph G, it follows that
(3)
μ
t
(
G
)
≤
χ
v
t
(
G
)
≤
μ
t
(
G
)
+
1
,
where μ
t
(
G
)
=
min
⁡
⁡
{
k
∣
(
k
i
+
1
)
≥
n
i
,
δ
≤
i
≤
Δ
}.In this paper, we introduce a variant of vertex-distinguishing total coloring of a graphG, which relaxes the restriction that the coloring is proper. We now present the detailed definition as follows.Definition 2.
LetG be a graph and k be a positive integer. A total coloring f of G using k colors is called a general vertex-distinguishing total k-coloring of G
(or k
-GVDTC of G briefly) if, for all u
,
v
∈
V
(
G
), C
f
(
u
)
≠
C
f
(
v
). The minimum number k for which G has a k
-GVDTC is the general vertex-distinguishing total chromatic number, denoted by χ
g
v
t
(
G
).It is evident thatχ
g
v
t
(
G
) does exist for any graph G. In this paper, we study the general vertex-distinguishing total coloring of some special classes of graphs and obtain the exact value of the general vertex-distinguishing total chromatic number of these graphs. Furthermore, we propose a conjecture on the upper bound of general vertex-distinguishing total chromatic number of a graph.


## 2. Main Results

We first present a trivial lower bound on the general vertex-distinguishing total chromatic number of a graph.Theorem 3.
LetG be a graph on n vertices. Then
(4)
χ
g
v
t
(
G
)
≥
⌈
log
⁡
2
(
n
+
1
)
⌉
.Proof.
Letχ
g
v
t
(
G
)
=
k. It follows that n
≤
(
k
1
)
+
(
k
2
)
+
⋯
+
(
k
k
)
=
2
k
-
1, so k
≥
⌈
log
⁡
2
(
n
+
1
)
⌉.Notice that the lower bound of Theorem3 can be attained in graphs, such as the n-vertex path P
n for n
=
1,2
,
…
,
7. One can readily check that χ
g
v
t
(
P
1
)
=
1 and χ
g
v
t
(
P
n
)
=
2 for n
=
2,3 and χ
g
v
t
(
P
n
)
=
3 for n
=
4,5
,
6,7.Theorem 4.
LetG be a graph without isolated vertices and isolated edges. Then
(5)
χ
g
v
t
(
G
)
≤
χ
g
v
d
′
(
G
)
.Proof.
Suppose thatf is a k-GVDEC of G. For any u
∈
V
(
G
), let f
(
u
)
=
f
(
u
v
), where u
v
∈
E
(
G
). Obviously, f is a k
-GVDTC of G.We now turn to investigating the general vertex-distinguishing total chromatic number of ann-vertex path.Theorem 5.
LetP
n be a path on n vertices, n
≥
1. Then
(6)
χ
g
v
t
(
P
n
)
=
⌈
3
n
+
9
n
2
+
125
27
3
+
3
n
-
9
n
2
+
125
27
3
⌉
.Proof.
Denote byP
n
=
v
1
v
2
⋯
v
n a path P
n with vertex set {
v
1
,
v
2
,
…
,
v
n
} and edge set {
v
1
v
2
,
v
2
v
3
,
…
,
v
n
-
1
v
n
}. Let χ
g
v
t
(
P
n
)
=
k, and let f be a k-GVDTC of P
n. Let α
k
=
(
k
-
1
1
)
+
(
k
-
1
2
)
+
(
k
-
1
3
), β
k
=
(
k
1
)
+
(
k
2
)
+
(
k
3
), γ
k
=
1
+
(
k
-
1
1
)
+
(
k
-
1
2
), and
(7)
k
*
=
⌈
3
n
+
9
n
2
+
125
27
3
+
3
n
-
9
n
2
+
125
27
3
⌉
.
Evidently, |
C
f
(
v
i
)
|
≤
3, and n
≤
β
k (which implies k
≥
k
*). In order to prove the conclusion, k
=
k
*, it suffices to give a k
*-GVDTC of P
n. When n
≤
7, it is not hard to construct the corresponding general vertex-distinguishing total colorings. Let n
≥
8. We first construct a k
*-GVDTC
f
′ of P
β
k recursively. Note that when n
=
β
k, it has k
*
=
k.
Procedure 1. Construct a 4-GVDTC
f
4 of P
β
4 (i.e., P
14) as follows: the vertices v
1
,
v
2
,
…
,
v
14 are colored by 1,3
,
4,2
,
3,1
,
4,2
,
3,4
,
3,4
,
4,1, respectively; the edges v
1
v
2
,
v
2
v
3
,
v
3
v
4
,
…
,
v
13
v
14 are colored by 1,3
,
1,1
,
2,4
,
2,2
,
2,3
,
3,4
,
4, respectively. It is easy to see that f
4 is a 4
-GVDTC of P
14.
Procedure 2. Construct a k-GVDTC
f
k of P
β
k based on a (
k
-
1
)-GVDTC
f
k
-
1 of P
β
k
-
1. Let f
k be
(8)
f
k
(
v
i
+
γ
k
)
=
f
k
-
1
(
v
i
)
+
1
,
i
=
1,2
,
…
,
α
k
-
1
;
f
k
(
v
α
k
+
γ
k
)
=
f
k
-
1
(
v
α
k
)
=
1
;
f
k
(
v
i
+
γ
k
v
i
+
1
+
γ
k
)
=
f
k
-
1
(
v
i
v
i
+
1
)
+
1
,
i
=
1,2
,
…
,
α
k
-
1
;
f
k
(
v
1
)
=
1
,
f
k
(
v
γ
k
)
=
k
;
v
2
,
v
3
,
…
,
v
γ
k
-
1 are colored by
(9)
k
-
1
,
k
︸
2
elements
,
k
-
2
,
k
-
1
,
k
︸
3
elements
,
…
,
2,3
,
…
,
k
︸
k
-
1
elements
;
whenk is even, v
1
v
2
,
v
2
v
3
,
v
3
v
4
,
…
,
v
γ
k
v
γ
k
+
1 are colored by(10)
1
︸
1
element
,
k
-
1,1
︸
2
elements
,
1
,
k
-
2,1
︸
3
elements
,
k
-
3,1
,
k
-
3,1
︸
4
elements
,
1
,
k
-
4,1
,
k
-
4,1
︸
5
elements
,
⋮
,
1
,
k
-
(
k
-
4
)
,
…
,
1
,
k
-
(
k
-
4
)
,
1
︸
k
-
3
elements
,
k
-
(
k
-
3
)
,
1
,
…
,
k
-
(
k
-
3
)
,
1
︸
k
-
2
elements
,
2,1
,
…
,
2,1
︸
k
-
2
elements
,
2,2
︸
2
elements
;
whenk is odd, v
1
v
2
,
v
2
v
3
,
v
3
v
4
,
…
,
v
γ
k
v
γ
k
+
1 are colored by(11)
1
︸
1
element
,
k
-
1,1
︸
2
elements
,
1
,
k
-
2,1
︸
3
elements
,
k
-
3,1
,
k
-
3,1
︸
4
elements
,
1
,
k
-
4,1
,
k
-
4,1
︸
5
elements
,
⋮
,
k
-
(
k
-
4
)
,
1
,
…
,
k
-
(
k
-
4
)
,
1
︸
k
-
3
elements
,
1
,
k
-
(
k
-
3
)
,
…
,
1
,
k
-
(
k
-
3
)
,
1
︸
k
-
2
elements
,
1,2
,
…
,
1,2
,
1
︸
k
-
2
elements
,
2,2
︸
2
elements
.It should be pointed out that when j is odd for j
∈
{
1,2
,
…
,
k
-
3
}, the colors’ form is k
-
j
,
1
,
k
-
j
,
1
,
…
,
k
-
j
,
1 with totally j
+
1 elements, and when j is even for j
∈
{
1,2
,
…
,
k
-
3
}, the colors’ form is 1
,
k
-
j
,
1
,
k
-
j
,
…
,
1
,
k
-
j
,
1 with j
+
1 elements in total.
According tof
k
-
1, we can see that, for any i
,
j
=
γ
k
+
1
,
γ
k
+
2
,
…
,
β
k
-
1, and i
≠
j, it follows that {
2
,
k
} is not a total color set of vertices v
i, 1
∉
C
f
k
(
v
i
), and C
f
k
(
v
i
)
≠
C
f
k
(
v
j
). In addition, C
1
,
C
2
,
…
,
C
γ
-
1 are as follows: {
1
} (1 item), {
{
1
,
k
-
1
}
,
{
1
,
k
-
1
,
k
}
} (2 items), {
{
1
,
k
-
2
}
,
{
1
,
k
-
2
,
k
-
1
}
,
{
1
,
k
-
2
,
k
}
} (3 items),
…,{
{
1
,
k
-
j
}
,
{
1
,
k
-
j
,
k
-
j
+
1
}, {
1
,
k
-
j
,
k
-
j
+
2
}
,
…
,
{
1
,
k
-
j
,
k
}
} (j
+
1 items),
…, and {
{
1,2
}
,
{
1,2
,
3
}
,
{
1,2
,
4
}
,
…
,
{
1,2
,
k
}
} (k
-
1 items). And C
f
k
(
v
γ
k
)
=
{
2
,
k
}. So, f
k is a k-GVDTC of P
β
k. We now show that P
n also has a k-GVDTC based on a k-GVDTC of P
β
k, for (
k
-
1
1
)
+
(
k
-
1
2
)
+
(
k
-
1
3
)
<
n
<
β
k.
Letr
=
β
-
n, and let f be a k-GVDTC of P
β
k constructed by Procedures 1 and 2. We first delete r vertices v
1
,
v
2
,
…
,
v
r from P
β
k. Obviously, the resulting graph, denoted by v
r
+
1
v
r
+
2
⋯
v
β
k, is isomorphic to P
n. Let f
′ be f
′
(
v
i
v
i
+
1
)
=
f
(
v
i
v
i
+
1
) for i
=
r
+
1
,
r
+
2
,
…
,
β
k
-
1; f
′
(
v
i
)
=
f
(
v
i
) for i
=
r
+
2
,
…
,
β; and f
′
(
v
r
+
1
)
=
1. Then f
′ is a k-GVDTC of P
n.
All the above show that the conclusion holds.According to Theorem5, we have the same conclusion on cycles. Let C
n
=
v
1
v
2
⋯
v
n
v
1 be an n-vertex cycle with vertex set {
v
1
,
v
2
,
…
,
v
n
} and edge set {
v
1
v
2
,
v
2
v
3
,
…
,
v
n
-
1
v
n
,
v
n
v
1
}.Corollary 6.
For any cycleC
n
(
n
≥
3
), one has
(12)
χ
g
v
t
(
C
n
)
=
⌈
3
n
+
9
n
2
+
125
27
3
+
3
n
-
9
n
2
+
125
27
3
⌉
.Proof.
LetC
n
=
v
1
v
2
⋯
v
n
v
1 and P
n
=
C
n
∖
v
1
v
n; let also
(13)
k
*
=
⌈
3
n
+
9
n
2
+
125
27
3
+
3
n
-
9
n
2
+
125
27
3
⌉
and let f be a k
*-GVETC of P
n, constructed by the method of Theorem 5. Then we can extend f to a k
*-GVETC of C
n by assigning color 1 to edge v
1
v
n. So, the conclusion holds.In the following (Theorem7 to Theorem 9), we discuss the general vertex-distinguishing total chromatic number of some kinds of special trees. Astar
S
n is the complete bipartite graph K
1
,
n (n
≥
1). Adouble star
S
m
,
n is a tree containing exactly two vertices that are not leaves (which are necessarily adjacent). Atristar
S
p
,
q
,
r is a tree with vertex set V
(
S
p
,
q
,
r
)
=
{
u
i
∣
i
=
0,1
,
…
,
p
}
∪
{
v
i
∣
i
=
0,1
,
…
,
q
}
∪
{
w
i
∣
i
=
0,1
,
…
,
l
} and edge set E
(
S
p
,
q
,
r
)
=
{
u
0
u
i
∣
i
=
1,2
,
…
,
p
}
∪
{
v
0
v
i
∣
i
=
1,2
,
…
,
q
}
∪
{
w
0
w
i
∣
i
=
1,2
,
…
,
r
}
∪
{
u
0
v
0
,
v
0
w
0
}, where p
,
q
,
r are positive integers.Theorem 7.
For a starS
n
(
n
≥
1
), one has
(14)
χ
g
v
t
(
S
n
)
=
{
2
,
n
=
1,2
;
⌈
8
n
+
1
-
1
2
⌉
,
n
≥
3
.Proof.
Whenn
=
1,2, the conclusion is trivial. For n
≥
3, let χ
g
v
t
(
S
n
)
=
k, and ⌈
(
8
n
+
1
-
1
)
/
2
⌉
=
k
′. Since, for any u
∈
V
(
S
n
)
∖
u
0 (u
0 is the vertex with d
S
n
(
u
0
)
≥
2), |
C
f
(
u
)
|
≤
2 for any k-GVDTC
f of S
n, it follows that n
≤
(
k
1
)
+
(
k
2
); that is, k
≥
k
′. In order to prove k
=
k
′, we need to show that there exists a k
′-GVDTC of S
n. Otherwise, let S
n
* be the graph with minimum n
* such that S
n
* does not have a k
′-GVDTC, where n
*
≤
n. Let u be a vertex of degree 1 in S
n
*. Consider the graph G
′
=
S
n
*
-
u, obtained from S
n
* by deleting the vertex u and its incident edge. By the assumption of S
n
*, G
′ has a k
′-GVDTC, denoted by f
′. In addition, by interchanging the colors of some vertex and its incident edge appropriately, we can assume |
C
f
′
(
u
0
)
|
≥
2. Since n
*
-
1
<
(
k
′
1
)
+
(
k
′
2
), there is at least one set {
a
,
b
}, for a
,
b
∈
{
1,2
,
…
,
k
′
}, which is not the total color set of the vertices of G
′. So, on the basis of f
′, in S
n
* we can color u and its incident edge u
u
0 by a and b, respectively. Obviously, the resulting coloring is a k
′-GVDTC of S
n
*.For two verticesu
,
v of a graph G, toidentify these two vertices is to replace them by a single vertex (denoted by u-v in this paper) incident to all the edges which were incident in G to either u or v. The resulting graph is denoted by G
/
{
u
,
v
}. In what follows, we denoted by [
1
,
k
] the set of {
1,2
,
…
,
k
}.Theorem 8.
LetS
m
,
n
(
m
≥
n
≥
1
) be a double star, and l
=
m
+
n. Then
(15)
χ
g
v
t
(
S
m
,
n
)
=
{
3
,
l
=
2,3
,
4,5
;
4
,
l
=
6
;
⌈
8
l
+
1
-
1
2
⌉
,
l
≥
7
.Proof.
Whenl
≤
6, the results are easy to be proved. When l
≥
7, let u
,
v be two vertices with degree more than 1, and G
′
=
S
m
,
n
/
{
u
,
v
}. Evidently, the graph G
′ is isomorphic to the star S
l. Let k
′
=
⌈
(
8
l
+
1
-
1
)
/
2
⌉. Since |
C
f
(
x
)
|
≤
2 for any x
∈
V
(
S
m
,
n
)
∖
{
u
,
v
}, we have χ
g
v
t
(
S
m
,
n
)
≥
k
′.
By Theorem7, G
′ contains a k
′-GVDTC
f
′. Evidently, |
C
f
′
(
x
)
|
≤
2 for any x
∈
V
(
G
′
)
∖
{
u
-
v
} and |
C
f
′
(
u
-
v
)
|
≤
k
′. If |
C
f
′
(
u
-
v
)
|
≤
2, then we can extend f
′ to a k
′-GVDTC of S
m
,
n by coloring vertices u
,
v and edge u
v with any three different colors in [
1
,
k
]
∖
{
f
′
(
u
-
v
)
}; if |
C
f
′
(
u
-
v
)
|
=
l
′
≥
3, we without loss of generality assume C
f
′
(
u
-
v
)
∖
f
′
(
u
-
v
)
=
[
1
,
l
′
]. Let E
u (resp., E
v) be the set of edges (except edge u
v) incident to u (resp., v) in S
m
,
n. We now extend f
′ to a k
′-GVDTC of S
m
,
n as follows. By the fact that there remain vertices u
,
v and edge u
v uncolored in S
m
,
n when f
′ is restricted to S
m
,
n, we consider the following two cases. First, one of u
,
v, say u, satisfies that C
f
′
(
E
u
) contains at most two elements. Assume C
f
′
(
E
u
)
⊆
{
1,2
}; we then color u
,
u
v
,
v by 2,3
,
c, respectively, where c
=
4 when C
f
′
(
E
u
)
≠
{
3,4
} and c
=
2 when C
f
′
(
E
u
)
=
{
3,4
}. The resulting coloring of S
m
,
n is also denoted by f
′. Then it follows in S
m
,
n that |
C
f
′
(
u
)
|
≥
3, |
C
f
′
(
v
)
|
≥
3, and 4
∉
C
f
′
(
u
) and 4
∈
C
f
′
(
v
). So, f
′ is a k
′-GVDTC of S
m
,
n. Second, |
C
f
′
(
E
v
)
|
≥
3 and |
C
f
′
(
E
u
)
|
≥
3; then we will further discuss two subcases.(1)
Consider|
C
f
′
(
E
u
)
|
=
|
C
f
′
(
E
v
)
|
=
k
′. Suppose that V
u (and V
v) is the set of vertices, except v (or u), adjacent to u (and v) in S
m
,
n. Because f
′ is a k
′-GVDTC of G
′, either V
u or V
v contains no vertices with total color set {
i
}, for some i
∈
{
1,2
,
…
,
k
′
}. Without loss of generality we assume that there is no vertex x
∈
V
u with C
f
′
(
x
)
=
{
i
}. For any vertex y in V
u such that C
f
′
(
y
)
=
{
i
,
j
} and f
′
(
y
u
)
=
i, interchange the two colors of y and y
u. The resulting coloring, still denoted by f
′, satisfies that C
f
′
(
E
u
) does not contain color i. Then we color u
,
u
v
,
v by any three colors in {
1,2
,
…
,
k
′
}
∖
{
i
} and obtain a k
′-GVDTC of S
m
,
n.
(2)
Consider|
C
f
′
(
E
u
)
|
<
k
′ or |
C
f
′
(
E
v
)
|
<
k
′; assume |
C
f
′
(
E
u
)
|
<
k
′ here. Let i
∉
C
f
′
(
E
u
). Color v by i and color u
,
u
v by any two colors in [
1
,
k
′
]
∖
{
i
}. Obviously, the resulting coloring is a k
′-GVDTC of S
m
,
n.
All the above show thatχ
g
v
t
(
S
m
,
n
)
≤
k
′. So, the conclusion holds.Theorem 9.
LetS
p
,
q
,
l be a tristar defined as above, and l
=
p
+
q
+
r. Then
(16)
χ
g
v
t
(
S
p
,
q
,
r
)
=
{
3
,
l
=
3,4
;
4
,
l
=
5,6
;
⌈
(
8
r
+
1
-
1
)
/
2
⌉
,
l
≥
7
.Proof.
Whenl
=
3,4, the conclusion is easy to be checked; when l
=
5 or 6, since |
V
(
S
p
,
q
,
r
)
|
≥
8 and (
3
1
)
+
(
3
2
)
+
(
3
3
)
=
7, it follows that χ
g
v
t
(
S
p
,
q
,
r
)
>
3. In addition, it is not hard to give a 4-GVDTC of V
(
S
p
,
q
,
r
) in each case of l
=
5 or 6, so χ
g
v
t
(
S
p
,
q
,
r
)
=
4; when l
≥
7, let k
′
=
⌈
(
8
r
+
1
-
1
)
/
2
⌉. Identify vertices u
0 and v
0 in S
p
,
q
,
r and let G
′
=
S
p
,
q
,
r
/
{
u
,
v
}. By Theorem 8, G
′ has a k
′-GVDTC
f
′. With the analogous analysis method of Theorem 8, we can also extend f
′ to a k
′-GVDTC of S
p
,
q
,
r. This shows χ
g
v
t
(
S
p
,
q
,
r
)
≤
k
′. On the other hand, for any k-GVDTC
f of S
p
,
q
,
r, it has that l
≤
(
k
1
)
+
(
k
2
); that is, k
≥
k
′. So, the result holds.In the above, we construct ak-GVDTC of a graph G by extending a k-GVDTC of graph G
′, where G
′ is the resulting graph of identifying two vertices of degree more than 1 in G. But this method does not always work. For instance, the graph G
/
{
u
,
v
} shown in Figure 1(b) has a 4-GVDTC, but the graph G shown in Figure 1(a) does not contain any 4-GVDTC. So any 4-GVDTC of G
/
{
u
,
v
} can not be extended to a 4-GVDTC of G.(a) A graph,G; (b) G
/
{
u
,
v
}.
(a)
(b)In the following we are devoted to the study of the general vertex-distinguishing chromatic number of fan graphF
n, wheel graph W
n, and complete graph K
n. Let G
,
H be two graphs such that V
(
G
)
∩
V
(
H
)
=
∅. The join G
+
H of G and H is a graph with vertex set V
(
G
+
H
)
=
V
(
G
)
∪
V
(
H
) and edge set E
(
G
+
H
)
=
E
(
G
)
∪
E
(
H
)
∪
{
u
v
∣
u
∈
V
(
G
)
,
v
∈
V
(
H
)
}. Afan graph
F
n is defined as the join of a path of n vertices and an isolated vertex. Awheel graph
W
n is defined as the join of a cycle of n vertices and an isolated vertex.Theorem 10.
LetF
n be a fan, n
≥
2; then
(17)
χ
g
v
t
(
F
n
)
=
{
3
,
n
=
2,3
,
…
,
6
;
4
,
n
=
7,8
,
…
,
14
;
k
,
n
≥
15
,
where (
k
-
1
1
)
+
(
k
-
1
2
)
+
(
k
-
1
3
)
+
(
k
-
1
4
)
<
n
≤
(
k
1
)
+
(
k
2
)
+
(
k
3
)
+
(
k
4
).Proof.
LetV
(
F
n
)
=
{
v
i
∣
i
=
0,1
,
…
,
n
} and E
(
F
n
)
=
{
v
1
v
2
,
v
2
v
3
,
…
,
v
n
-
1
v
n
}
∪
{
v
0
v
i
∣
i
=
1,2
,
…
,
n
}. When n
≤
14, the conclusion is easy to show. We now consider the case of n
≥
15 (which implies k
≥
5). Since (
k
-
1
1
)
+
(
k
-
1
2
)
+
(
k
-
1
3
)
+
(
k
-
1
4
)
<
n and |
C
f
(
v
i
)
|
≤
4 for i
∈
[
1
,
n
], we can easily deduce that χ
g
v
t
(
F
n
)
≥
k. So, it suffices to show that F
n contains a k-GVDTC. In particular, we prove that F
n contains a k-GVDTC such that the total color set of v
0 contains at least 5 elements. By induction on n. When n
=
15, it is not hard to construct such a k
(
≥
5
)-GVDTC of F
n. Suppose that, for any F
n
′, n
′
<
n, there exists a k-GVDTC of F
n
′. Consider the fan graph F
n
-
1, and let f be a k-GVDTC of F
n
-
1. Anyway, we can assume that, for any color x
∈
[
1
,
k
], there is an edge v
i
v
i
+
1 for some i
∈
[
1
,
n
-
1
] such that f
(
v
i
v
i
+
1
)
=
x (If not, we can permutate x and f
(
v
i
v
i
+
1
)).
Note that for any edgev
i
v
i
+
1 of F
n
-
1, i
∈
[
1
,
k
], if we replace this edge by a vertex u and connect this vertex to v
0, v
i, and v
i
+
1, then the resulting graph, denoted by F
n
-
1
v
i
,
u
,
v
i
+
1, is isomorphic to F
n. We will use this to construct a k-GVDTC of F
n based on f. It is obvious that there remain only 4 uncolored elements, v
i
u
,
u
v
i
+
1
,
u
v
0, and u in F
n
-
1
v
i
,
u
,
v
i
+
1, if we restrict f to F
n
-
1
v
i
,
u
,
v
i
+
1. We need to consider the following 2 cases.
Case
1. There exist colors x
,
y
,
z
∈
[
1
,
k
] such that {
x
,
y
,
z
}
∉
C
f
(
F
n
-
1
). Let v
i
v
i
+
1 be the edge with f
(
v
i
v
i
+
1
)
=
x, i
∈
[
1
,
n
-
1
]. In F
n
-
1
v
i
,
u
,
v
i
+
1, let f
(
u
v
i
)
=
f
(
u
v
i
+
1
)
=
x, f
(
u
v
0
)
=
y, and f
(
u
)
=
z, and the resulting coloring is still denoted by f. Evidently, in F
n
-
1
v
i
,
u
,
v
i
+
1, C
f
(
u
)
=
{
x
,
y
,
z
}; meanwhile C
f
(
v
i
) and C
f
(
v
i
+
1
) are the same as those in F
n
-
1, and |
C
f
(
v
0
)
|
≥
5. So, f a k-GVDTC of F
n
-
1
v
i
,
u
,
v
i
+
1.
Case
2. Four different colors x
,
y
,
z
,
w
∈
[
1
,
k
] such that {
x
,
y
,
z
,
w
}
∉
C
f
(
F
n
-
1
). Select an edge v
i
v
i
+
1, i
∈
[
1
,
n
-
1
], for which f
(
v
i
v
i
+
1
)
=
x. Since f is a k-GVDTC of F
n
-
1, C
f
(
v
i
)
∖
C
f
(
v
i
+
1
) contains at least one element (here we assume |
C
f
(
v
i
)
|
≥
|
C
f
(
v
i
+
1
)
|), say c. Obviously, c
≠
x, c
∈
C
f
(
v
i
), and c
∉
C
f
(
v
i
+
1
) in F
n
-
1. We can permutate the colors so that c
∈
{
y
,
x
,
w
} and f
(
v
i
)
=
c in F
n
-
1, say c
=
y. Then, in F
n
-
1
v
i
,
u
,
v
i
+
1, erase the color of vertex v
i and recolor it by color x, and let f
(
u
v
i
)
=
y, f
(
u
v
i
+
1
)
=
x, f
(
u
v
0
)
=
z, and f
(
u
)
=
w. Obviously, in F
n
-
1
v
i
,
u
,
v
i
+
1, it follows that C
f
(
u
)
=
{
x
,
y
,
z
,
w
}, C
f
(
v
i
) and C
f
(
v
i
+
1
) are the same as those in F
n
-
1, and |
C
f
(
v
0
)
|
≥
5. So, f a k-GVDTC of F
n
-
1
v
i
,
u
,
v
i
+
1.
All of the above show thatF
n has a k-GVDTC.Theorem 11.
LetW
n be a wheel graph, n
≥
2; then
(18)
χ
g
v
t
(
W
n
)
=
{
3
,
n
=
2,3
,
…
,
6
;
4
,
n
=
7,8
,
…
,
14
;
k
,
n
≥
15
,
where (
k
-
1
1
)
+
(
k
-
1
2
)
+
(
k
-
1
3
)
+
(
k
-
1
4
)
<
n
≤
(
k
1
)
+
(
k
2
)
+
(
k
3
)
+
(
k
4
).We omit the proof for Theorem11, since it is analogous to that of Theorem 10.Theorem 12.
For a complete graphK
n, n
≥
1, one has
(19)
χ
g
v
t
(
K
n
)
=
1
+
⌈
log
⁡
2
n
⌉
.Proof.
Whenn
<
10 the conclusion is easy to show. So we assume n
≥
10.
Denote byV
(
K
n
)
=
{
v
1
,
v
2
,
…
,
v
n
} and {
1,2
,
…
,
k
} the set of k colors. For integer l
=
⌈
n
/
2
⌉, we construct a l-GVDTC
f
′ of K
n as follows: let f
′
(
v
i
)
=
i for any i
∈
[
1
,
l
]; f
′
(
v
i
v
j
)
=
1 for i
≠
j, i
∈
[
1
,
l
], and j
∈
[
1
,
n
]; f
(
v
i
)
=
i
-
l
+
2 for i
∈
[
l
+
1
,
n
-
2
]; f
′
(
v
i
v
j
)
=
2 for i
≠
j, i
∈
[
l
+
1
,
n
-
2
], and j
∈
[
l
+
1
,
n
]; f
′
(
v
n
-
1
v
n
)
=
3; f
′
(
v
n
-
1
)
=
4; f
′
(
v
n
)
=
5. One can readily check that C
f
′
(
v
1
)
=
{
1
}, C
f
′
(
v
i
)
=
{
1
,
i
} for i
=
1,2
,
…
,
l; C
f
′
(
v
i
)
=
{
1,2
,
i
-
l
+
2
} for i
=
l
+
1
,
l
+
2
,
…
,
n
-
2; C
f
′
(
v
n
-
1
)
=
{
1,2
,
3,4
}; and C
f
′
(
v
n
-
1
)
=
{
1,2
,
3,5
}. Thus, f
′ is a l-GVDTC of K
n, which shows χ
g
v
t
(
K
n
)
≤
l.
Suppose thatχ
g
v
t
(
K
n
)
=
k and f is a k-GVDTC of K
n. Since for any two vertices v
i
,
v
j (i
≠
j
∈
[
1
,
k
]), C
f
(
v
i
)
∩
C
f
(
v
j
)
≠
∅, one can see that there is at most one vertex whose total color set contains only one color. If there is a vertex v with |
C
(
v
)
|
=
1, without loss of generality assume C
(
v
)
=
{
1
}; then the total color set of each vertex contains color 1, which indicates
(20)
n
≤
1
+
(
k
-
1
1
)
+
(
k
-
1
2
)
+
⋯
+
(
k
-
1
k
-
1
)
=
2
k
-
1
.
If there is no vertex whose total color set contains only one color, then for each v
i it has |
C
(
v
i
)
|
≥
2. Since, for any vertex v
j
≠
v
i, |
C
(
v
i
)
∩
C
(
v
j
)
|
≥
1, it follows that C
(
v
) and [
1
,
k
]
∖
C
(
v
) can not be two total color sets with respect to f. This implies n
≤
2
k
-
1. So k
≥
1
+
⌈
log
⁡
2
n
⌉.
To provek
=
1
+
⌈
log
⁡
2
n
⌉, we need to show that K
n has a (
1
+
⌈
log
⁡
2
n
⌉
)-GVDTC. In particular, we show that any K
n has a (
1
+
⌈
log
⁡
2
n
⌉
)-GVDTC such that for each color c
∈
[
1,1
+
⌈
log
⁡
2
n
⌉
] there is at least one vertex in K
n being colored by c.
We prove this by induction onn. When n
=
10, 5-GVDTC is the f
′ defined above for n
=
10
,
l
=
5, where C
f
′
(
v
1
)
=
{
1
}. Consider the graph K
n
-
v
n obtained from K
n by deleting vertex v
n and its incident edges. Obviously, K
n
-
v
n is isomorphic to K
n
-
1. By the induction hypothesis, K
n
-
1 has a (
1
+
⌈
log
⁡
2
n
-
1
⌉
)-GVDTC, say f, such that for each color c
∈
[
1,1
+
⌈
log
⁡
2
n
-
1
⌉
] there is at least one vertex of K
n
-
1 being colored by c. Since n
≤
2
k
-
1, there must be some set C (denoted by {
c
1
,
c
2
,
…
,
c
l
}
)
∉
C
f
(
K
n
-
1
). We consider the following two cases.(1)
Consider⌈
log
⁡
2
n
-
1
⌉
=
⌈
log
⁡
2
n
⌉. By the induction hypothesis, each color c
i
∈
[
1,1
+
⌈
log
⁡
2
n
-
1
⌉
] appears at a vertex. Without loss of generality assume f
(
v
i
)
=
c
i for i
=
1,2
,
…
,
l. Then, f is extended to a (
1
+
⌈
log
⁡
2
n
-
1
⌉
)-GVDTC of K
n via coloring v
n by one of the colors in [
c
1
,
c
2
,
…
,
c
l
]; coloring v
n
v
i for i
=
1,2
,
…
,
l by c
i; and coloring v
n
v
j for j
=
l
+
1
,
…
,
n
-
1 by one of the colors in C
f
(
v
j
) (v
j
∈
V
(
K
n
-
1
)).
(2)
Consider⌈
log
⁡
2
n
-
1
⌉
=
⌈
log
⁡
2
n
⌉
-
1. Then on the basis of f, we only need to color v
n and all of its incident edges in K
n by color 1
+
⌈
log
⁡
2
n
-
1
⌉.
One can readily check that the resulting coloring ofK
n in the above two cases is (
1
+
⌈
log
⁡
2
n
⌉
)-GVDTCs of K
n such that each color in [
1,1
+
⌈
log
⁡
2
n
⌉
] appears at a vertex of K
n. Hence, K
n has a (
1
+
⌈
log
⁡
2
n
⌉
)-GVDTC, and the conclusion holds.In the following, we present a trivial upper bound of the general vertex-distinguishing total chromatic number of the join graph of two graphs.Theorem 13.
SupposeG, H are two simple graphs and G
∩
H
=
∅. Then
(21)
χ
g
v
t
(
G
+
H
)
≤
χ
g
v
t
(
G
)
+
χ
g
v
t
(
H
)
.Proof.
LetV
(
G
)={
u
i
∣
i
=
1,2
,
…
,
m
} and V
(
H
)
=
{
v
i
∣
i
=
1,2
,
…
,
n
}. Suppose that f
1 is a χ
g
v
t
(
G
)-GVDTC of G and f
2 is a χ
g
v
t
(
H
)-GVDTC of H, where the sets of colors of f
1 and f
2 are C
1 and C
2 (C
1
∩
C
2
=
∅), respectively.
Definef as f
(
u
i
v
j
)
=
f
1
(
u
i
)
(
or
f
2
(
v
j
)
)
,
i
=
1,2
,
…
,
m
;
j
=
1,2
,
…
,
n.
Combining coloringsf
1
,
f
2
,
f, we can obtain a (
χ
g
v
t
(
G
)
+
χ
g
v
t
(
H
)
)-GVDTC of G
+
H.


## 3. Remarks

Based on the above results, we propose two conjectures as follows.Conjecture 14.
LetG be a graph without isolated vertices. Then
(22)
χ
g
v
t
(
G
)
≤
⌈
n
2
⌉
.Conjecture 15.
LetG be a connected graph on n vertices. Then
(23)
χ
g
v
t
(
G
)
≤
1
+
⌈
log
⁡
2
n
⌉
.Note that if Conjecture15 is true, then Conjecture 14 is true. On the other hand, if Conjecture 14 is true, then the upper bound cannot be improved. For instance, the graph G contains exactly three K
2 components. It is easy to show that χ
g
v
t
(
G
)
=
3.In addition, there is a very interesting observation about the general vertex-distinguishing total chromatic number.Observation 1.
LetH be a subgraph of a graph G. Then it possibly follows that
(24)
χ
g
v
t
(
H
)
>
χ
g
v
t
(
G
)
.As an illustration of this observation, we consider the pathP
15 and the fan graph F
14. P
15 is a subgraph of F
14, while χ
g
v
t
(
P
15
)
(
=
5
)
>
χ
g
v
t
(
F
14
)
(
=
4
).



---

*Source: 849748-2014-08-03.xml*