Adjacent Vertex Distinguishing I-total Coloring of Outerplanar Graphs

(College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,China)

§1.Introduction

All graphs considered in this article are simple,undirected and finite.LetGbe a graph with vertex setV(G)and edge setE(G).AnI-total coloring ofGis a mappingφ:V(G)∪E(G)→{1,2,···,k}such that no adjacent vertices receive the same color and no adjacent edges receive the same color.TheI-total chromatic numberχi(G)ofGis the smallest integerksuch thatGhas anI-total coloring.LetCφ(v)={φ(v)∪φ(uv)|uv∈E(G)}denote the set of colors assigned to a vertexvand those edges incident tov.AnI-total coloringφofGis adjacent vertex distinguishing,or ank-AVDIT coloring,ifCφ(u)/=Cφ(v)wheneveruv∈E(G).The adjacent vertex distinguishingI-total chromatic number(G)is the smallest integerksuch thatGhas ank-AVDIT coloring.

Let∆ andδdenote the maximum degree and the minimum degree of a graphG,respectively.By definition,it is evident that(G)≥∆(G)for any graphG.

A planar graph is called outerplanar if there is an embedding ofGinto the Euclidean plane such that all the vertices are incident to the unbounded face.An outerplane graph is a particular embedding of an outerplanar graph.

Zhang et al in[1]investigated firstly the adjacent vertex distinguishing total coloring of graphs.Chen proved the adjacent vertex distinguishing total chromatic of graphs with∆(G)=3 in[2].Moreover,Wang et al.have determined the adjacent vertex distinguishing total chromatic of outerplanar graphs in[3].The notion of adjacent vertex distinguishingI-total coloring of graphs was introduced by Zhang et al in[4].The adjacent vertex distinguishingI-total coloring ofPn□Cmandk-multi-Mycieski graph were studied in[5-6].Yang et al in[7-8]showed that the adjacent vertex distinguishingI-total coloring ofPm□Kn,corona graphsCm·CnandCm·Kn.Recently,Chen et al determined the adjacent vertex distinguishingI-total coloring of complete graphKnand the treeT.

In this paper,we characterize the adjacent vertex distinguishingI-total chromatic number of outerplane graphs.More precisely,we prove the following.

Main TheoremLetGbe an outerplane graph with∆(G)≥3.Then∆(G)(G)≤∆(G)+1 and= ∆(G)+1 ifGcontains two adjacent vertices of maximum degree.

§2.Structural Lemmas

LetGbe an outerplane graph.LetF(G)denote the set of faces inG.Forf∈F(G),we useb(f)to denote the boundary walk offand writef=[u1u2···un]ifu1,u2,···,unare all the vertices ofb(f)traversed once in cyclic order.Ak-vertex is a vertex of degreek.A 1-vertex is also said to be a leaf.

We de fine some con figurations as follows.

(C1)A vertexvof degree at most 3 is adjacent to a leaf.

(C2)A pathx1x2···xn,n≥4,withdG(x1)/=2,dG(xn)/=2 anddG(xi)=2 for alli=2,3,···,n−1.

(C3)Ak-vertexv,k≥4,is adjacent to a leaf andk−3 vertices of degree≤2.

(C4)A 3-face[uv1v2]satis fiesdG(u)=2 anddG(v1)=3.

(C5)Two 3-faces[u1v1x]and[u2v2x]satisfydG(x)=4 anddG(u1)=dG(u2)=2.

Lemma 1[3]Every connected outerplane graphGwith at least two vertices contains one of the con figurations(C1)to(C5).

Lemma 2[3]Every connected outerplane graphGwith∆(G)≤3 contains one of the following con figurations

(B1)A vertexvadjacent to at most one vertex that is not a leaf.

(B2)A pathx1x2x3x4such thatdG(x1)=3,and each ofx2andx3is either a 2-vertex,or a 3-vertex that is adjacent to a leaf.

(B3)A 3-face[uxy]withdG(x)=3 such that eitherdG(u)=2,ordG(u)=3 anduis adjacent to a leaf.

Lemma 3[3]Every connected outerplane graphGwith∆(G)=4 without adjacent 4-vertices contains one of the following con figurations

(A1)A vertexvwithdG(v)/=3 is adjacent to a leaf.

(A2)A 3-vertex is adjacent to at least two leaves.

(A3)A pathx1x2x3x4such thatdG(x1)=3 and each ofx2andx3is either a 2-vertex,or a 3-vertex that is adjacent to a leaf.

(A4)A 3-face[uxy]withdG(x)=3 such that eitherdG(u)=2,ordG(u)=3 anduis adjacent to a leaf.

Lemma 4[3]Every connected outerplane graphGwith∆(G)=3 and without adjacent 3-vertices contains one of the following con figurations

(D1)A leaf.

(D2)A cycleC=x1x2···xn,withn≥3,such thatdG(x1)=3 anddG(xi)=2 for alli=2,3,···,n.

§3.Main Results

Given an outerplane graphG,we write|T(G)|=|V(G)|+|E(G)|.The proof of the Main Theorem is divided into two cases:∆(G)=3 and∆(G)≥4.

Lemma 5LetGbe a connected graph with ∆(G)≤2.Then(G)≤3.

ProofSinceGis a connected graph with∆(G)≤2,thenGis either a path or a cycle.

IfGis a path,thenGmust be a tree.Chen et al in[9]had proved that(T)≤∆(T)+1 for a treeTwith ordern≥2.So we have(G)≤∆(G)+1≤3.

IfGis a cycle,letC=v1v2···vnv1(n≥3).We only need to give a 3-AVDIT coloringφofC.We consider the following two cases.

Case 1Whenn≡1(mod 2),we color the edgesv1v2,v2v3,···,vn−2vn−1,vn−1vnwith 1,2,1,2,···,and color the edgevnv1with 3.For the verticesvk(1≤k≤n)ofC,letφ(vk)=3 ifk≡1(mod 2),k≤n−2 and letφ(vk)=φ(vk−1vk)ifk≡0(mod 2),k≤n−1.Finally,we color the vertexvnbyφ(vn−1vn).

Case 2Whenn≡0(mod 2),let(X,Y)be a bipartition ofV(C),whereX={v1,v3,···,vn−1}andY={v2,v4,···,vn}.We color the edgesv1v2,v2v3,···,vn−1vn,vnv1with 1,2,1,2,···.Then color all the vertices ofXwith 3 and color each vertex inYwith some color of its incident edges.

Proposition 6IfGis a connected graph with two adjacent vertices of maximum degree,Then(G)≥∆(G)+1.

Theorem 1IfGis an outerplane graph with ∆(G)≤3,then(G)≤4.

ProofThe proof proceeds by induction on|T(G)|.If|T(G)|≤5,the Theorem holds trivially.Suppose thatGis an outerplane graph with∆(G)≤3 and|T(G)|≥6.By the induction assumption,any outerplane graphHwith∆(H)≤3 and|T(H)|＜|T(G)|has a 4-AVDIT coloring.

We may assume thatGis connected since(G)=max(Gi)}and ∆(G)=max{∆(Gi)},where both maxima are taken over all componentsGiofG.By Lemma 5,any connected graphGwith∆(G)≤2 has a 3-AVDIT coloring.So we can suppose thatGis connected and∆(G)=3.

By Lemma 2,Gcontains one of con figurations(B1)～(B3).To complete the proof,we need to handle separately every possible case.

(B1)Gcontains a vertexvadjacent to at most one vertex that is not a leaf.

Letv1,v2,···,vnbe all the neighbors ofvwithdG(v1)=dG(v2)=···dG(vn−1)=1 anddG(vn)≥1.Clearly,2≤n≤3.LetH=G−{v1,v2,···,vn−1}.Then,His an outerplane graph with ∆(H)≤3 with|T(H)|＜|T(G)|,hence it has a 4-AVDIT coloringφusing colors 1,2,3,4.

IfdG(v)=2,dG(v2)=2,letu1/=vbe the second neighbor ofv2.We colorvv1with a color inCCφ(v2),v1with a color inCCφ(v).

IfdG(v)=2,dG(v2)=3,letu1,u2/=vbe the other neighbors ofv2.We color properlyvv1ifφ(v)=φ(vv2).Otherwise,we colorvv1withφ(v)such that|Cφ(v)|=2.Finally,we colorv1with a color inCCφ(v).

IfdG(v)=3,dG(v3)=1,Gis a star with order 4.We can easily give a 4-AVDIT coloringφofG.

IfdG(v)=3,dG(v3)=2,letu1/=vbe the second neighbor ofv3.We recolorvwith a color inCCφ(v3),and colorvv1,vv2with different colors inC{φ(vv3)}.Then we color properlyv1andv2.

IfdG(v)=3,dG(v3)=3,letu1,u2/=vbe the other neighbors ofv3.When|Cφ(v3)|=3,we recolorvwith a color inCCφ(v3)and denote the color ofvbyφ(v).Then we colorvv1,vv2with different colors inC{φ(vv3)}and color properlyv1andv2.When|Cφ(v3)|=4,we colorvv1,vv2with different colors inC{φ(vv3)},and recolorvwithφ(vv3).Then we color properlyv1andv2.

(B2)Gcontains a pathx1x2x3x4such thatdG(x1)=3,and each ofx2andx3is either a 2-vertex,or a 3-vertex that is adjacent to a leaf.

Fori∈{2,3},letbe a leaf adjacent toxiprovidedxiis a 3-vertex.

(B 2.1)If bothx2andx3are 2-vertex,thenG−x2x3has a 4-AVDIT coloringφusing colors 1,2,3,4.We need to consider some subcases.

Case 2.1.1dG(x4)=1.

We colorx2x3with a color inC{φ(x1x2),φ(x3x4)}and denote the color ofx2x3byφ(x2x3).Then we recolorx3with a color inC({φ(x2x3)}∪Cφ(x4)).Ifφ(x1x2)=φ(x3),φ(x2x3)=φ(x1),we recolorx2with a color inCCφ(x3).Now,we need to recolorx2x3withφ(x2).Otherwise,there must exist a color can recolorx2in{φ(x1x2),φ(x2x3)}.

Case 2.1.2dG(x4)=2.

Letx5/=x3be the second neighbor ofx4.If|Cφ(x4)|=2,then the proof can be given with a similar argument as in the case 2.1.1.If|Cφ(x4)|=3,we colorx2x3with a color inC{φ(x1x2),φ(x3x4)}.Then we recolorx3with a color in{φ(x2x3),φ(x3x4)}{φ(x4)}when we omit the color ofx2.Now,if|Cφ(x1)|=4,then we colorx2with a color inC{φ(x1),φ(x2x3),φ(x3x4)}.If|Cφ(x1)|=3,we need to consider the following situations.

Ifφ(x2x3)/∈Cφ(x1)andφ(x2x3)/=φ(x3),then we recolorx2withφ(x2x3).

Ifφ(x2x3)/∈Cφ(x1)andφ(x2x3)=φ(x3),we recolorx2with a color inC{φ(x1),φ(x1x2),φ(x2x3)}.

Ifφ(x2x3)∈Cφ(x1)andφ(x2x3)/=φ(x3),we recolorx2withCCφ(x1)whenφ(x3)∈Cφ(x1)and recolorx2with a color in{φ(x1x2),φ(x2x3)}{φ(x1)}whenφ(x3)/∈Cφ(x1).

Ifφ(x2x3)∈Cφ(x1)andφ(x2x3)=φ(x3),we recolorx2with a color inCCφ(x1).

Case 2.1.3dG(x4)=3.

Letx5,x6/=x3be the other neighbors ofx4.We colorx2x3with a color inC{φ(x1x2),φ(x3x4)}.There must exist a color in{φ(x2x3),φ(x3x4)}can recolorx3when we omit the color ofx2.Then we consider the color ofx2.If|Cφ(x1)|=4,we recolorx2with a color inC({φ(x1)}∪Cφ(x3)).If|Cφ(x1)|=3,the proof can be given with a similar argument as in the Case 2.1.2.

(B3)Gcontains a 3-face[uxy]withdG(x)=3 such that eitherdG(u)=2,ordG(u)=3 anduis adjacent to a leafu′.

(B 3.1)dG(y)=dG(u)=2.

By the induction assumption,G−{uy}has a 4-AVDIT coloringφusing colors 1,2,3,4.If|Cφ(x)|=4,we coloruywith a color different from the color ofux,xy,and recoloruwithφ(xu),ywithφ(xy).If|Cφ(x)|=3,we color or recoloruanduywith a color inCCφ(x),ywith a color inC{φ(x),φ(u)}.

(B 3.2)dG(y)=2,dG(u)=3.

By the induction assumption,G−{u′}has a 4-AVDIT coloringφusing colors 1,2,3,4.If|Cφ(x)|=4,we recolorywithφ(xy),uwithφ(xu).Then we coloruu′with a color inC{φ(xu),φ(uy)}.If|Cφ(x)|=3,we recolorywith{φ(xy),φ(uy)}{φ(x)}after omitting the color ofu.Then we consider recoloringu.We color or recoloruu′anduwith a color inCCφ(x)whenφ(uy)∈Cφ(x).Otherwise,we coloruu′with a color inC{φ(xu),φ(uy)}and recoloruwith a color inC{φ(x),φ(y)}.

(B 3.3)dG(y)=3,dG(u)=3.

Letx′/=u,ybe the third neighbor ofxandy′/=u,xbe the third neighbor ofy.By the induction assumption,G−{u′}has a 4-AVDIT coloringφusing colors 1,2,3,4.

If|Cφ(x)|=4,|Cφ(y)|=3,we coloruu′withCCφ(y)whenφ(xu)∈Cφ(y)or color properlyuu′whenφ(xu)/∈Cφ(y).Then we recoloruwith a color in{φ(xu),φ(yu),φ(uu′)}{φ(x),φ(y)}.

If|Cφ(x)|=3,|Cφ(y)|=3,we coloruu′withC{φ(xu),φ(uy),φ(xy)}and recoloruwith a color in{φ(xu),φ(uy),φ(uu′)}{φ(x),φ(y)}.

(B 3.4)dG(y)=3,dG(u)=2.

Lety′(/=u,x)be the third neighbors ofy.Letf′denote the face adjacent to[uxy]withxyas a common edge.We need to consider some subcases depending on the size off′.

Case 3.4.1dG(f′)=3,i.e.,x′is identical toy′.By the induction assumption,G−{u}has a 4-AVDIT coloringφusing colors 1,2,3,4.

IfdG(x′)=2,i.e.,Gis a graph of order 4 obtained fromK4by removing an edge.We can give a 4-AVDIT coloringφofG.We color{x′,xx′,uy}with 1,{y,x′y}with 2,{x,xy}with 3,and{u,ux}with 4.

IfdG(x′)=3,lett(/=x,y)be the third neighbor ofx′.

If|Cφ(x′)|=3,letCφ(x′)={1,2,3},φ(xx′)=1,φ(x′t)=2,φ(x′y)=3 andφ(x′)=a,thena∈{1,2,3}.Ifa=1,2,we color{u,uy}with 1,uxwith 2,ywith 3,and{xy,x}with 4.Ifa=3,we color{u,uy}with 1,ywith 2,uxwith 3,and{xy,x}with 4.

If|Cφ(x′)|=4,letCφ(x′)={1,2,3,4},φ(xx′)=1,φ(x′t)=2,φ(x′y)=3,andφ(x′)=4.We coloruywith 1,{x,xy}with 2,ywith 3{u,ux}with 4.

Case 3.4.2dG(f′)=4,i.e.,x′is adjacent toy′.

(i)IfdG(x′)=dG(y′)=2,we can give a 4-AVDIT coloringφofG.We color{ux,x}with 1,{xy,x′y′,y,x′}with 2,{u,uy,xx′}with 3,and{yy′,y′}with 4.

(ii)IfdG(x′)=3 anddG(y′)=2(without loss generality,we may assume that),letx′′(/=x,y′)be the third neighbor ofx′.By the induction assumption,G−{uy}has a 4-AVDIT coloringφusing colors 1,2,3,4.Letφ(xx′)=1,φ(x′y′)=2,φ(x′x′′)=3 andφ(x′)=a,thena∈{1,2,3,4}.

Ifa=1,2,3,we coloruywith 1,{y,xy}with 2,{u,ux}with 3,{x,y′,yy′}with 4.Ifa=4,we colorxwith 1,{y,xy}with 2,{u,ux,y′,yy′}with 3,uywith 4.

(iii)IfdG(x′)=dG(y′)=3,letx′′(/=x,y′)be the third neighbor ofx′,andy′′(/=y,x′)be the third neighbor ofy′.By the induction assumption,G−{uy}has a 4-AVDIT coloringφusing colors 1,2,3,4.Letφ(xx′)=1,φ(x′y′)=2,φ(x′x′′)=3,φ(x′)=a,φ(yy′)=b,φ(y′)=c,thena∈{1,2,3,4},b∈{1,3,4}.

a=1.Ifb=1,we colorywith 1,{u,ux}with 2,uywith 3,{x,xy}with 4.Ifb=3,we color{y,uy}with 1,{u,ux}with 2,{x,xy}with 4.Ifb=4,we color or recolor{y,uy}with 1,xwith 2,xywith 3,{u,ux}with 4.

a=2.Ifb=1,c=1,3,we recolorxwith 1,{u,ux}with 2,uywith 3,{y,xy}with 4.Ifb=1,c=4,we color or recolorxwith 1,{u,ux}with 2,{y,uy}with 3,xywith 4.Ifb=3,c=1,3,we color{x,uy}with 1,{u,ux}with 2,{y,xy}with 4.Ifb=3,c=4,we color or recolor{x,uy}with 1,{u,ux}with 2,ywith 3,xywith 4.Ifb=4,c=1,4,we color or recoloruywith 1,{u,ux}with 2,{y,xy}with 3,xwith 4.Ifb=4,c=3,we color or recolor{y,uy}with 1,{u,ux}with 2,xywith 3,xwith 4.

a=3.Ifb=1,we color or recolor{u,ux}with 2,{y,uy}with 3,{x,xy}with 4.Ifb=3,we color or recoloruywith 1,{u,ux}with 2,ywith 3,{x,xy}with 4.Ifb=4,we color or recoloruywith 1,xwith 2,{y,xy}with 3,{u,ux}with 4.

a=4.Ifb=1,we color or recolor{u,ux}with 2,{x,xy}with 3,{y,uy}with 4.Ifb=3,we color or recolor{x,uy}with 1,{u,ux}with 2,{y,xy}with 4.Ifb=4,we color or recolor{x,uy}with 1,{u,ux}with 2,xywith 3,ywith 4.

Case 3.4.3dG(f′)≥5,i.e.,x′is not adjacent toy′.

LetH=G−{u,x,y}+x′y′.By the induction assumption,Hhas a 4-AVDIT coloringφusing colors 1,2,3,4.Without loss generality,we may assume thatφ(x′)=1,φ(y′)=3.Ifφ(x′y′)=1,then,inG,we color{xx′,yy′}with 1,{x,uy}with 2,{u,ux}with 3,{y,xy}with 4.Ifφ(x′y′)=2,then,inG,we color{y,uy}with 1,{u,xx′,yy′}with 2,{x,ux}with 3,xywith 4.Ifφ(x′y′)=3,then,inG,we color{u,uy}with 1,{y,ux}with 2,{xx′,yy′}with 3,{x,xy}with 4.

Theorem 2IfGis an outerplane graph with∆(G)=3 without adjacent 3-vertices,then(G)=3.

ProofThe lower bound that(G)≥3 is trivial.We prove the upper bound3 by induction on the vertex number|V(G)|.If|V(G)|=4,thenGis eitherK1,3or a graph obtained fromK1,3by joining a pair of leaves.It is easy to verify that(G)=3 for both these cases.LetGbe a connected outerplane graph with∆(G)=3 and|V(G)|≥5 and having no adjacent 3-vertices.By lemma 4,Gcontains(D1)or(D2).

(1)IfGcontains(D1),i.e.,a leafvadjacent to a vertexu,letH=G−v.By the induction assumption,Hhas a 3-AVDIT coloringφusing colors 1,2,3.We consider the degree ofu.

Case 1IfdG(u)=2,letx(/=v)be the second neighbor ofu.

If|Cφ(x)|=2,we recoloruwith a color inCCφ(x)and{v,uv}with a color inC{φ(u),φ(u x)}.IfdG(x)=2 and|Cφ(x)|=3,we recoloruwithφ(ux)and color{v,uv}with a color inC{φ(u)}.IfdG(x)=3 and|Cφ(x)|=3,we coloruanduvwith a color inC{φ(x),φ(ux)},and colorvwith a color inCCφ(u).

Case 2IfdG(u)=3,letu1,u2(/=v)be the other neighbors ofu.SinceGhas no adjacent 3-vertex and|V(G)|≥5,we can see thatdG(ui)≤2 fori=1,2 and it is impossible thatdG(u1)=dG(u2)=1.

(2)IfGcontains(D2),i.e.,a cycleC=x1x2···xn,withn≥3,such thatdG(x1)=3 anddG(xi)=2 for alli=2,3,···,n,lety(/=x2,xn)be the third neighbor ofx1.We see thatyis not a 3-vertex.LetH=G−{x1xn}.By the induction assumption,Hhas a 3-AVDIT coloringφusing colors 1,2,3.

Case 1|Cφ(y)|≤2.

Ifn≡0(mod 2),we recolor the vertices and the edges ofC.First,we recolor{x1,x1x2}with a color inCCφ(y),x2x3with a color inC{φ(x1y),φ(x1x2)}.Next,we color the edgesx3x4,x4x5,···,xn−1xn,xnx1with colorsφ(x1x2),φ(x2x3),φ(x1x2),φ(x2x3),···.For the verticesvk(1≤k≤n)ofC,we colorvkwithφ(x2x3)whenk≡0(mod 2)and colorvkwithφ(x1y)whenk≥3 andk≡1(mod 2).

Ifn≡1(mod 2),we recolor the vertices and the edges ofC.First,we color{x1,x1x2}with a color inCCφ(y),andx2x3withφ(x1y).Next,we color the edgesx3x4,x4x5,···,xn−2xn−1,xn−1xnwith colorsφ(x1x2),φ(x2x3),φ(x1x2),φ(x2x3),···,and colorxnx1with a color inC{φ(x1y),φ(x1x2)}.For the verticesvk(1≤k≤n)ofC,we colorvkwithφ(x2x3)whenk≡0(mod 2),and colorvkwithφ(x1xn)whenk≥3 andk≡1(mod 2).

Case 2|Cφ(y)|=3.

We can see thatdG(y)=2.Lety1(/=x1)be the second neighbor ofyand|Cφ(y1)|≤2.We can recolor{y,x1y}with a color inCCφ(y1)such that|Cφ(y)|=2.Then we give a similar proof to the case of|Cφ(y)|≤2.

Theorem 3IfGis an outerplane graph with ∆(G)≥4,then(G)≤∆(G)+1.

ProofWe prove the Theorem by induction on|T(G)|.If|T(G)|≤9,Gis a star with order 5,the Theorem holds clearly.Suppose thatGis a connected outerplane graph with∆(G)≥4 and|T(G)|≥10.By the induction assumption,every outerplane graphHwith∆(H)≤∆(G)and|T(H)|＜|T(G)|has∆(H)+1≤∆(G)+1.

By Lemma 1,Gcontains one of the con figurations(C1)～(C5).Since∆(G)≥4,then we have|C|≥∆(G)+1≥5.

(C1)Gcontains a vertexvwithdG(v)≤3 which is adjacent to a leaf.

Letuibe the neighbors ofvfor 1≤i≤3 anddG(u1)=1,dG(ui)≥2 for 2≤i≤3.LetH=G−u1.ThenHis a connected outerplane graph with|T(H)|＜|T(G)|and∆(H)≤∆(G).By the induction assumption,Hhas a(∆(G)+1)-AVDIT coloringφusing colors 1,2,···,∆(G)+1.

Case 1.1dG(v)=2.

IfdG(u2)=2,or 3,we colorvu1with a color inCCφ(u2)andu1with a color inCCφ(v).

IfdG(u2)≥4,we only need to color{vu1,u1}with a color inC{φ(v)∪φ(vu2)}.

Case 1.2dG(v)=3.

Suppose thatφ(vu2)=1,φ(vu3)=2.If|{3,4,5}∩Cφ(ui)|≥2 for alli=2,3,we colorvu1with 3.If|{3,4,5}∩Cφ(ui)|≤1 for alli=2,3,we colorvu1with a color in{3,4,5}({3,4,5}∩(Cφ(u2)∪Cφ(u3))).If|{3,4,5}∩Cφ(u2)|≥2,|{3,4,5}∩Cφ(u3)|≤1,we colorvu1with a color in{3,4,5}({3,4,5}∩Cφ(u3)).Then we recolorvwith a color in{φ(vu1),φ(vu2),φ(vu3)}{φ(u2),φ(u3)}.

(C2)Gcontains a pathx1x2···xnwithdG(x1)≥3,dG(xn)≥3 anddG(xi)=2 for alli=2,3,···,n−1,wheren≥4.

LetH=G−x2x3.ThenHis a connected outerplane graph with with|T(H)|＜|T(G)|and∆(H)≤∆(G).By the induction assumption,Hhas a(∆(G)+1)-AVDIT coloringφusing colors 1,2,···,∆(G)+1.

Case 2.1n=4.If|Cφ(x1)|=3,we color properlyx2x3.Then we recolorx3with a color in{φ(x2x3),φ(x3x4)}{φ(x4)}.Finally,we recolorx2with a color inC({φ(x1)}∪Cφ(x3))whenφ(x2x3)/∈Cφ(x1).Otherwise,we recolorx2with a color inC({φ(x3)}∪Cφ(x1)).If|Cφ(x1)|≥4,we color properlyx2x3.Then we recolorx3with a color in{φ(x2x3),φ(x3x4)}{φ(x4)}.Finally,we recolorx2with a color inC({φ(x1)}∪Cφ(x3)).

Case 2.2n≥5.We color properlyx2x3.Then we recolorx2with a color in{φ(x1x2),φ(x2x3)}{φ(x1)},x4with a color in{φ(x3x4),φ(x4x5)}{φ(x5)}.Finally,we recolorx3with a color inC(Cφ(x2)∪Cφ(x4)).

(C3)Gcontains a vertexvwith neighborsv1,v2,···,vk,k≥4,such thatdG(v1)=1 anddG(vi)≤2 for alli=2,3,···,k−2.

For 2≤i≤k−2,ifviis 2-vertex,we denote byui/=vthe second neighbor ofvi.It follows from(C2)thatdG(ui)≥3.By the induction assumption,G−v1has a(∆(G)+1)-AVDIT coloringφusing colors 1,2,···,∆(G)+1.We may assume thatφ(vvi)=ifori=2,3,···,k.Since∆(G)≥dG(v)=k,|C|≥∆(G)+1≥k+1.Thusk+1∈C.

Ifk+1∈(Cφ(vk−1)∩Cφ(vk)),we colorvv1with 1.Ifk+1/∈(Cφ(vk−1)∪Cφ(vk)),we colorvv1withk+1.If 1∈(Cφ(vk−1)∩Cφ(vk)),we colorvv1withk+1.If 1/∈(Cφ(vk−1)∪Cφ(vk)),we colorvv1with 1.If{1,k+1}⊆Cφ(vk−1)Cφ(vk)or{1,k+1}⊆Cφ(vk)Cφ(vk−1),we colorvv1withk+1.

Now suppose that 1∈Cφ(vk−1)Cφ(vk)andk+1∈Cφ(vk)Cφ(vk−1),say.IfdG(v2)=1,we recolor(or color)vv2withk+1 andvv1with 1.IfdG(v2)=2,we recolor(or color)vv2with a colora∈{1,k+1}{φ(v2u2)},vv1with a color in{1,k+1}{a},and then recolorv2with a color in{φ(vv2),φ(v2u2)}{φ(u2)}.Finally,we recolor properlyv.

(C4)Gcontains a 3-face[uv1v2]withdG(u)=2 anddG(v1)=3.

Letz/=u,v2be the third neighbor ofv1.Lety1,y2,···,ymbe the neighbors ofv2different fromuandv1.

Case 4.1m=0.Suppose thatdG(z)=d,thend≤∆(G)and the edgev1zis a cut edge ofG.By the induction assumption,G−uv2has a(∆(G)+1)-AVDIT coloringφusing colors 1,2,···,∆(G)+1.Then we only need to coloruv2with a color inCCφ(v1),coloruwithφ(uv2),and colorv2with a color in{φ(uv1),φ(v1v2)}{φ(v1)}.

Case 4.2m≥1.By the induction assumption,G−uv1has a(∆(G)+1)-AVDIT coloringφusing colors 1,2,···,∆(G)+1.

(4.2.1)Ifm=1,the proof is similar to the case(B3)in Theorem 1.

(4.2.2)Ifm=2,we consider the following cases.

(i)If|Cφ(z)|≤2,we color properlyuv1.Then we recolorv1with a color in{φ(uv1),φ(v1v2),φ(v1z)}{φ(v2),φ(z)},anduwith a color inC({φ(v2)}∪Cφ(v1)).

(ii)If|Cφ(z)|=3,we coloruv1with a color inC({φ(uv2)}∪Cφ(z))whenφ(v1v2)∈Cφ(z)and color properlyuv1whenφ(v1v2)/∈Cφ(z).Then we recolorv1with a color in{φ(uv1),φ(v1v2),φ(v1z)}{φ(v2),φ(z)}after omitting the color ofu.Finally,we recoloruwith a color inC({φ(v2)}∪Cφ(v1)).

(iii)If|Cφ(z)|≥4,we coloruv1with a color inC{φ(uv2),φ(v1v2),φ(v1z)}.Then we recolorv1with a color in{φ(uv1),φ(v1v2),φ(v1z)}{φ(v2),φ(z)}after omitting the color ofu.Finally,we recoloruwith a color inC({φ(v2)}∪Cφ(v1)).

(4.2.3)Assume thatm≥3.We obtained that∆(G)≥5 and|C|≥∆(G)+1≥6.We color properlyuv1.If|Cφ(z)|≤3,we recolorv1with a color inC({φ(v2)}∪Cφ(z)),uwith a color inC({φ(v2)}∪Cφ(v1)).Otherwise,we recolorv1with a color in{φ(uv1),φ(v1v2),φ(v1z)}{φ(v2),φ(z)},uwith a color inC({φ(v2)}∪Cφ(v1)).

(C5)Gcontains two 3-faces[u1v1x]and[u2v2x]such thatdG(x)=4 anddG(u1)=dG(u2)=2.

Ifv1is a 2-vertex orv2is a 2-vertex,thenG−u1v1orG−u2v2has a(∆(G)+1)-AVDIT coloringφusing colors 1,2,···,∆(G)+1.We can easily extend the coloring to the whole graphG.

Ifv1orv2is a 3-vertex,the proof is similar to the case(C4).

Now we assume thatdG(vi)≥4 fori=1,2.Letz1,z2,···,zmbe the neighbors ofv1different fromxandu1.Lety1,y2,···,ynbe the neighbors ofv2different fromxandu2.Thenm≥2 andn≥2.

Ifm,n≥3,then any(∆(G)+1)-AVDIT coloringφofG−xu1can be easily extended to the whole graphG.Otherwise,assume thatn≥2 andm=2 by symmetry.By the induction assumption,G−xu1has a(∆(G)+1)-AVDIT coloringφusing colors 1,2,···,∆(G)+1.We need to consider two subcases as follows:

Case 1n≥3.Obviously,we have|C|≥∆(G)+1≥5+1=6.Letb=CCφ(v1).Ifb/∈{φ(xu2),φ(xv2)},we colorxu1withb.Otherwise,we properly colorxu1.Then we recolorxwith a color in{φ(xu1),φ(xv1),φ(xu2),φ(xv2)}{φ(v1),φ(v2),φ(u2)}and recolor properlyu1.

Case 2n=2.SincedG(v2)=4≤∆(G),then|C|≥∆(G)+1≥5.

(2.1) If|Cφ(v1)|=|Cφ(v2)|=5,we colorxu1with a color different from the colors ofxv1,xu2,xv2,u1v1.Then we recolorxwith a color in{φ(xv1),φ(xu1),φ(xu2),φ(xv2)}{φ(v1),φ(u2),φ(v2)}.Finally,we color properlyu1.

(2.2) If|Cφ(v1)|=|Cφ(v2)|=4,we colorxu1with a color different from the colors ofu1v1,xv1,xv2,xu2.After omitting the colors ofu1,v1,u2,v2,we recolorxwith a color inC{φ(xu1),φ(xu2),φ(xv1),φ(xv2)}.Then,we recolorv1with a color in{φ(xv1),φ(v1u1),φ(v1z1),φ(v1z2)}{φ(z1),φ(z2),φ(x)}andv2with a color in{φ(xv2),φ(v2u2),φ(v2y1),φ(v2yz2)}{φ(y1),φ(y2),φ(x)}.Finally,we recolor properlyu1andu2.

(2.3)If|Cφ(v1)|=4,|Cφ(v2)|=5,letbdenote a color inCCφ(v1).Ifb∈{φ(xv2),φ(xu2)},we color properlyxu1.Otherwise,we colorxu1withb.Then we recolorxwith a color in{φ(xv1),φ(xv2),φ(xu1),φ(xu2)}{φ(v1),φ(v2),φ(u2)}and recolor properlyu1.

(2.4)If|Cφ(v1)|=5,|Cφ(v2)|=4,letcdenote a color inCCφ(v2).Ifc/=φ(u1v1),c/∈{φ(xv1),φ(xu2)},we colorxu1withc.Ifc/=φ(u1v1),c∈{φ(xv1),φ(xu2)},we color properlyxu1.Ifc=φ(u1v1),c/∈{φ(xv1),φ(xu2)},we colorxu1withφ(xu2)and recolorxu2withc.Ifc=φ(u1v1),c∈{φ(xv1),φ(xu2)},that isφ(u1v1)=φ(xu2)=c,we color properlyxu1.Finally,we recolorxwith a color in{φ(xv1),φ(xv2),φ(xu1),φ(xu2)}{φ(v1),φ(v2),φ(u2)},and recolor properlyu1.

Combining Proposition 6,Theorem 1,Theorem 2 and Theorem 3,we complete the proof of the Main Theorem.

We find that many graphGwith∆(G)≥4 and without adjacent vertices of maximum degree satisfy(G)= ∆(G).So we propose the following Conjecture 1.

Conjecture 1IfGis an outerplane graph with∆(G)≥4 and without adjacent vertices of maximum degree,theG)= ∆(G).

[1]ZHANG Zhong-fu,CHEN Xiang-en,LI Jing-wen,et al.On adjacent-vertex-distinguishing total coloring of graphs[J].Sci China Ser A,2005,48:289-299.

[2]CHEN Xiang-en.On the adjacent vertex distinguishing total coloring numbers of graphs with∆=3[J].Discrete Mathematics,2008,308:4003-4007.

[3]WANG Yi-qiao,WANG Wei-fan.Adjacent vertex distinguishing total colorings of outerplanar graphs[J].Journal of combinatorial optimization,2010,19(2):123-133.

[4]ZHANG Zhong-fu,WOODALL D R,YAO Bing,et al.Adjacent vertex-distinguishingI-total coloring of graphs[EB/OL].(2008-06-12)http://202.201/18.40:8080/mas 5/.

[5]YANG Xiao-ya.Adjacent vertex-distinguishingI-total colorings ofPn□Cm[J].Pure and Applied Mathematics,2012,28(6):757-764.

[6]TIAN Jing-jing.Adjacent vertex-distinguishingI-total chromatic number of some kinds ofk-multi-Mycieski graph[J].Computer Engineering and Applications,2012,48(25):39-41.

[7]YANG Sui-yi,GAO Yu-ping,HE Wan-sheng.Adjacent vertex-distinguishingI-total coloring ofPm□Kn[J].Mathematics in Practice and Theory,2013,43(1):212-218.

[8]YANG Sui-yi,HE Wan-sheng,WEN Fei.Adjacent vertex-distinguishingI-total coloring of corona graphsCm·CnandCm·Kn[J].Pure and Applied Mathematics,2011,27(3):327-333.

[9]CHEN Xiang-en,GAO Yu-ping,YAO Bing.Not necessarily proper total colourings which are adjacent vertex distinguishing[J].International Journal of Computer Mathematics,2013,9(11):2298-2307.