Adjacent vertex-distinguishing total colorings of ∨Kt

Feng Yun Lin Wensong

(Department of Mathematics, Southeast University, Nanjing 211189, China)

Proposition1[1]IfGis a graph of ordern, thenχvt(G)≤n+2.

AVDTC is related to vertex distinguishing proper edge colorings of graphs, which is first examined by Burris and Schelp[2]and further discussed by Bazgan et al[3-4]. This type of coloring is further extended to require only adjacent vertices to be distinguished[5]and it is in turn extended to proper total colorings[6].

Proposition2[6]IfGis a graph with two adjacent vertices of the maximum degree, then

χat(G)≥Δ(G)+2

By deleting an edge or two from a complete graphK2n+1, Zhang et al.[6]and Chen[7]obtained the adjacent vertex-distinguishing total chromatic number of such graphs.

Please refer to Ref.[8] for undefined terminologies and notations in this paper.

The following useful lemma can be found in Ref.[9].

Lemma1[9]Letnbe an integer andn≥2, then

(1)

Theorem1Ifs≥t≥2, then

Theorem2Let 2≤s

Theorem3Let 2≤s(s+1)2-2, then

q1+q2+…+q(s+1)/2+q(s+3)/2=s+t+1

(2)

(3)

(4)

(5)

That is

t≤(s+t+1)-(q(s+3)/2-s)

(6)

q(s+3)/2≤2s+1

(7)

From Eq.(4), we obtain

(8)

which is a contradiction.

(9)

(10)

(11)

(12)

That is

t≤(s+t+1)-(q(s+2)/2-s)

(13)

q(s+2)/2≤2s+1

(14)

Sincet>(s+1)2-2, from (11) we obtain

(15)

which is a contradiction.

[1]Zhang Z, Qiu P, Xu B, et al. Vertex-distinguishing total coloring of graphs [J].ArsCombin, 2008,87(2): 33-45.

[2]Burris A C, Schelp R H. Vertex-distinguishing proper edge-colourings [J].JGraphTheory, 1997,26(2):73-82.

[3]Bazgan C, Harkat-Benhamdine A, Li H, et al. On the vertex-distinguishing proper edge-coloring of graphs [J].JCombinTheorySerB, 1999,75(2): 288-301.

[4]Balister P N, Bollobs B, Schelp R H. Vertex distinguishing colorings of graphs withΔ(G)=2 [J].DiscreteMath, 2002,252(2): 17-29.

[5]Zhang Z, Liu L, Wang J. Adjacent strong edge coloring of graphs [J].ApplMathLett, 2002,15(5): 623-626.

[6]Zhang Z, Chen X, Li J, et al. On adjacent-vertex-distinguishing total coloring of graphs [J].SciChinaSerA, 2005,48(3): 289-299.

[7]Chen X. Adjacent-vertex-distinguishing total chromatic numbers onK2n+1-E(P3) [J].IntJPureApplMath, 2004,13(1): 19-27.

[8]Bondy J A, Murty U S R.Graphtheory[M]. New York: Springer, 2008.

[9]Hulgan J. Concise proofs for adjacent vertex-distinguishing total colorings [J].DiscreteMath, 2009,309(8): 2548-2550.

[10]West D B.Introductiontographtheory[M]. 2nd ed. London: Prentice Hall, 2001.