Discrete Mathematics 309 (2009) 2548–2550

Contents lists available at ScienceDirect

Discrete Mathematics
journal homepage: www.elsevier.com/locate/disc

Note

Concise proofs for adjacent vertex-distinguishing total colorings

Jonathan Hulgan
Department of Mathematical Sciences, The University of Memphis, Memphis, TN, 38152, USA

article info a b s t r a c t

Article history: Let G = (V , E ) be a graph and f : (V ∪E ) → [k] be a proper total k-coloring of G. We say that
Received 14 November 2007 f is an adjacent vertex- distinguishing total coloring if for any two adjacent vertices, the set
Received in revised form 19 May 2008 of colors appearing on the vertex and incident edges are different. We call the smallest k
Accepted 2 June 2008
for which such a coloring of G exists the adjacent vertex-distinguishing total chromatic
Available online 16 July 2008
number, and denote it by χat (G). Here we provide short proofs for an upper bound on
the adjacent vertex-distinguishing total chromatic number of graphs of maximum degree
Keywords:
Adjacent vertex-distinguishing total
three, and the exact values of χat (G) when G is a complete graph or a cycle.
coloring © 2008 Elsevier B.V. All rights reserved.
Adjacent vertex-distinguishing total
chromatic number

1. Introduction

Let G = (V , E ) be a simple graph. A proper total k-coloring of G is a mapping f : (V ∪ E ) → [k] such that no two adjacent
vertices receive the same color, no two incident edges receive the same color, and no vertex and incident edge receive the
same color. Given such a coloring f , for any vertex v ∈ V let C (v) = {f (v)} ∪ {f (uv) : uv ∈ E (G)}. For every pair of adjacent
vertices uv ∈ E, if C (u) 6= C (v) then we say that f is an adjacent vertex distinguishing total coloring (AVDTC). We call
the smallest k for which such a coloring of G exists the adjacent vertex-distinguishing total chromatic number, denoted by
χat (G).
This coloring is related to vertex-distinguishing proper edge colorings of graphs, first examined by Burris and Schelp [1]
and further discussed by many others, including Bazgan, et al. [2] and Balister, et al. [3]. This type of coloring was later
extended to require only adjacent vertices to be distinguished by Zhang et al. [4], which was in turn extended to proper
total colorings [5].
Zhang et al. in [5] determined χat (G) for many basic families of graphs, including cycles, complete graphs, complete
bipartite graphs, and trees. Additionally, the following bound on χat (G) in terms of the maximum degree of a graph ∆(G)
was conjectured.

Conjecture 1 ([5]). Let G be a simple graph. Then χat (G) ≤ ∆(G) + 3.

Wang in [6] was able to prove this bound for the case ∆(G) = 3 by employing subdivision graphs and intricate case
analysis. In this note we present a more elementary proof of this bound as well as more concise proofs for determining
χat (G) when G is a complete graph or a cycle.

2. Complete graphs and cycles

Zhang et al. in [5] determined χat (G) for complete graphs and cycles. Here we give concise proofs for these results. The
first is due to A. Gyárfás.

E-mail address: [email protected].

0012-365X/$ – see front matter © 2008 Elsevier B.V. All rights reserved.
doi:10.1016/j.disc.2008.06.002
 J. Hulgan / Discrete Mathematics 309 (2009) 2548–2550 2549

n
n+1 if n is even
Proposition 2. χat (Kn ) = n+2 if n is odd
for n ≥ 2.

Proof. An optimal AVDTC for complete graphs can be easily obtained from the standard near-factorization of K2m+1 , defined
as follows: on vertex set [2m + 1], for every i ∈ [2m + 1] let Fi be the set of edges (i − x, i + x) for x = 1, 2, . . . , m according
to modulo 2m + 1 arithmetic (here we denote 0 by 2m + 1 for notational convenience). If vertices are colored with their
vertex labels and edges in Fi are colored with i, then we have a proper total coloring of K2m+1 with 2m + 1 colors. If one
vertex is removed, an AVDTC of K2m is obtained and if two vertices are removed, an AVDTC of K2m−1 is obtained.
The first statement holds for any near-factorization, and the second follows from the fact that in the standard near-
factorization above, there are no four-cycles in the union of two color classes. Suppose there exists a four-cycle with edges
colored a and b. This means the set of labels of vertices involved can be expressed as both {a − i, a + i, a − j, a + j} and
{b − k, b + k, b − `, b + `} for some i, j, k, ` ∈ {1, 2, . . . , m}. Since these two sets must be equal modulo 2m + 1, their sums
must also be equal. Therefore 4a ≡ 4b mod (2m + 1); but since (4, 2m + 1) = 1, this implies a = b, a contradiction.
It is clear that 2m + 1 colors are needed for K2m . To show that 2m + 1 colors are necessary for K2m−1 , suppose an AVDTC
with 2m colors is possible. If a color is absent from the color set of one vertex, it must be present at every other vertex because
all color sets must be distinct. Additionally, every vertex must be colored distinctly, and so by the pigeonhole principle there
exists a color i that appears only on one vertex. It follows that every remaining vertex is incident to an edge colored by i.
However, an odd number of vertices remain and obviously no perfect matching exists between them, a contradiction.


Proposition 3. χat (Cn ) = 4 for n ≥ 4.

Proof. If n is even, alternately color the vertices of the cycle 1 and 2, and alternately color the edges 3 and 4. This is an AVDTC
because it is clearly proper and the color sets of adjacent vertices are distinguished by their vertex color. If n is odd, again
alternately color the vertices and edges of the cycle as in the even case except for one vertex, say v1 , and its incident edges.
Thus we assume v2 is colored 1, vn is colored 2, and both have an incident edge colored 3. Then color v1 by 4, v1 v2 by 2, and
vn v1 by 1. 

3. Graphs with ∆(G ) = 3

Wang in [6] provides a case analysis detailing an AVDTC in six colors for graphs with maximum degree three. Here we
give a much shorter proof using a different approach.

Definition 4. Let G = (V , E ) be a graph and f : (V ∪ E ) → [k] a proper total coloring. Define CE ⊆ [k] to denote the set of
colors that appear on the edges of G and CV ⊆ [k] to denote the set of colors that appear on the vertices of G. We say that f
is an almost disjoint total coloring if |CE ∩ CV | ≤ 1.

Lemma 5. An almost disjoint proper total coloring of a graph is an AVDTC.

Proof. Observe that two adjacent vertices have identical color sets only if the color appearing on each vertex is used to color
an incident edge of the other. However, this cannot happen since the colors used to color two adjacent vertices cannot both
be used to also color edges. 

Theorem 6. If G is a graph with ∆(G) = 3 and G 6= K4 , then there exists an almost disjoint total 6-coloring of G.

Proof. We claim there exists a partial almost-disjoint 6-coloring f of G with the following properties:
(1) The vertices of G are colored 1, 2, and 3.
(2) The edges incident to the 3 color class are colored 4, 5, and 6.
(3) The edges incident to the 1 and 2 color classes are colored 3, 4, 5, 6, or remain uncolored.
The graph G has a proper vertex coloring with colors 1, 2, and 3 by Brooks’ Theorem. Consider the bipartite graph formed
by all edges with one endpoint in color class 3, and the other endpoint in color classes 1 or 2; by König’s Theorem, these
edges can be 3-colored with colors 4, 5, and 6. Therefore there exist partial 6-colorings of G that satisfy Properties (1) and
(2). Consider the collection F of colorings of G with these two properties. We claim there exists a coloring in F that satisfies
Property (3) with no uncolored edges.
Suppose this is not the case; choose a coloring f ∈ F with the fewest number of uncolored edges. Given such an f , we can
create another partial 6-coloring f 0 ∈ F such that the number of uncolored edges is one less, thus deriving a contradiction.
Consider an edge uv that is left uncolored by f . By Property (3), uv must be incident to a 1 vertex and a 2 vertex. If C (u)
and C (v) have a common color then exactly three of the colors 3, 4, 5, and 6 are found at u or v , and so we may choose the
fourth color with which to color uv in f 0 .
Suppose C (u) and C (v) have no common color. Without loss of generality, suppose u has a 4 edge and a 3 edge, call it
uw , and v has a 5 edge and a 6 edge. Now consider C (w). If C (w) 6= C (v), in f 0 we can color uv 3 and recolor uw with either
5 or 6, whichever is not present at w .
2550 J. Hulgan / Discrete Mathematics 309 (2009) 2548–2550

Suppose C (w) = C (v). Consider the longest path P consisting of edges alternately colored 4 and 5 originating from u and
switch the colors of each edge along it. If P does not terminate at v , we may now color uv 4 in f 0 since the color 4 no longer
appears at u. If P does terminate at v , it obviously cannot terminate at w and so in f 0 we may color uv 3 and recolor uw 4.
This exhausts all possibilities, and therefore there exists an almost disjoint total 6-coloring of G. 

Corollary 7. Let G be a graph with ∆(G) = 3. Then χat (G) ≤ 6.

Proof. By Proposition 2, χat (K4 ) = 5. If G 6= K4 , by Theorem 6 there exists an almost disjoint total 6-coloring of G, which is
an AVDTC by Lemma 5. 
These results above confirm Conjecture 1 of Zhang et al. [5] for ∆(G) = 3. Although complete graphs of odd order show
the conjectured bound is sharp for even maximum degree, many maximum degree three graphs, including the K4 , K3,3 , and
Petersen graphs, have an AVDTC with only 5 colors. Therefore, we propose the following problem.

Problem 8. For a graph G with ∆(G) = 3, is the bound χat (G) ≤ 6 sharp?

Acknowledgements

I would like to acknowledge András Gyárfás and my advisor Jenő Lehel for their extremely helpful insight and suggestions.

References

[1] A. Burris, R. Schelp, Vertex-distinguishing proper edge-colorings, Journal of Graph Theory 26 (2) (1997) 73–82.
[2] C. Bazgan, A. Harkat-Benhamdine, H. Li, M. Woźniak, On the vertex-distinguishing proper edge-coloring of graphs, Journal of Combinatorial Theory,
Series B 75 (2) (1999) 288–301.
[3] P. Balister, B. Bollobás, R. Schelp, Vertex distinguishing colorings of graphs with ∆(G) = 2, Discrete Mathematics 252 (2) (2002) 17–29.
[4] Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Applied Mathematics Letters 15 (5) (2002) 623–626.
[5] Z. Zhang, X. Chen, J. Li, B. Yao, X. Lu, J. Wang, On adjacent-vertex-distinguishing total coloring of graphs, Science in China Series A Mathematics 48
(2005) 289–299.
[6] H. Wang, On the adjacent vertex-distinguishing total chromatic numbers of the graphs with ∆(G) = 3, Journal of Combinatorial Optimization 14
(2007) 87–109.