The Problems Of Adjacent Vertex Distinguishing Coloring Of Graphs And Two Special Total Labelings Of Graphs

The coloring problem of graphs and some other graph theories are all from the study of the celebrated four color problem.The coloring problem of graphs is one of primary fields in the study of graph theories. It plays an important role in the combinatorial mathematics and our living.As the development of science,some scholars presented and studied a few coloring problems with different restrictions.The vertex distinguishing edge coloring originated in network problem was studied in [l],and a lot of new coloring problems are proposed continuously. The adjacent vertex distinguishing edge coloring(adjacent strong edge coloring) and the (adjacent) vertex distinguishing total coloring which had a application in data transmission were first in-troduced by Zhang Zhongfu,they proposed the following two definitions:Definition 1 G is a given simple connected graph and│V(G)│≥2,let k be a positive integer,and f is a mapping,f:E(G)→{1,2,…k},for any vertex u∈V(G),we denote C(u)={f(uw)│uw∈E(G),w∈V(G)}.if(1) for any uv,uw∈E(G),f(uv)≠f(uw);(2) for any uv G E(G),C(u)≠C(v).then f is called a adjacent vertex distinguishing edge coloring of G.χ'as(G)= min{k│G has a k-adjacent vertex distinguishing edge coloring}.Definition 2 G is a given simple connected graph and│V(G)│≥2,let k be a positive integer,and f is a mapping,f:V(G)∪E(G)→{1,2,…k},for any vertex u∈V(G),we denote C(u)={f(u)∪f(uw)│uw∈E(G),w∈V(G)}.if(1)for any uv,uw∈E(G),f(uv)≠f(uw);(2)for any uv∈E(G),f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);(3)for any uv∈E(G),C(u)≠C(v).then f is called a adjacent vertex distinguishing total coloring of G.χat(G)= min{k│G has a k-adjacent vertex distinguishing total coloring}.As the restriction was so strong that the problem was resolved only on some graphs such as tree,circle,complete graphs,some planar graphs etc..According to those results,Zhang Zhongfu gave two conjectures of graphs:Conjecture 1 If G is a simple connected graph with at least 3 vertices and G≠C5 thenχ'as(G)≤Δ(G)+2.Conjecture 2 If G is a simple connected graph with at least 3 vertices thenχat(G)≤Δ(G)+3.In 2007,Hajo Broersma varied the classic vertex coloring and put the restrictions only on the backbone of G.This new kind coloring was called BackBone coloring.Sun lei and Sun Meijiao use this cogitation and put the conditions of the adjacent vertex distinguishing edge coloring and the adjacent vertex distinguishing total coloring on the spanning tree of G.So we propose the following two definitions:Definition 3 G is a given simple connected graph,let k be a positive inte-ger,and f is a proper edge coloring of G,f:E(G)→{1,2,…k},let T be a spanning tree of G,C(u)={f(uw)│w∈N(u)},if any edge uv∈E(T) satisfies C(u)≠C(v),then f is called a T-adjacent vertex distinguishing edge coloring of G.χ'Tas(G,T)=min{k│G has a k-T-adjacent vertex distinguishing edge coloring}.Definition 4 G is a given simple connected graph,let k be a positive integer,and f is a proper total coloring of G,f:V(G)∪E(G)→{1,2,…k},let T be a spanning tree of G,C(u)={f(u)∪f(uw)│w∈N(u)},if any edge uv∈E(T) satisfies C(u)≠C(v),then f is called a T- adjacent vertex distinguishing total coloring of G.XTat(G, T)=min{k│G has a k-T-adjacent vertex distinguishing total coloring}.The restrictions in the two definitions are weaker than that in adjacent vertex distinguishing edge(total) coloring which were proposed by Zhang Zhongfu,so this kind of new coloring problem was called weak adjacent vertex distinguishing coloring problem.The frequency assignment problem is that of assigning a frequency to each radio transmitter so that interfering transmitters are assigned frequencies whose separation is not in a set of disallowed separations. In the channel assignment problem,the follow-ing situation occurs:we need to assign radio frequency bands to transmitters.In order to avoid interference,if two stations are too close,then the separation of the channels as-signed to them has to be at least two.Moreover,if the distance between two stations is two,then they must receive different channels.If this problem was inverted to the coloring problem of graph theory,it was the L(2,1)-labeling problem which was produced by Griggs and Yeh in 1992.In 2000,G.J.Cahang etc.generalized this problem to the L(p,1)-labeling.The L(p,1)-labeling of a graph G is an integer assignment L to the vertex set V(G) such that:(1)│L(u)-L(v)│≥p if dG(u,v)=1;(2)│L(u)-L(v)│≥1 if dG(u,v}=2.The first subdivision of graph G is the graph obtained by replacing each edge of G with a path of length 2.The L(p, l)-labeling of the first subdivision of graph G is a special total coloring of G.This kind of total coloring is (p,1)-total labeling introduced by Havet and YuDefinition 5 Let p be an positive integer,a k-(p,1)-total labeling of a graph G is a mappin f:V(G)∪E(G)→{0,1,…,k},such that:(1)for any two adjacent vertices u,v of G, having│f(u)-f(v)│≥1;(2)for any two adjacent edges e, e' of G, having│f(e)-f(e')│≥1;(3)for a vertex u and its incident edge e of G, having│f(u)-f(e)│≥p. We call such an assignment a(p,1)-total labeling of G.The span of a(p,1)-total labeling is the difference between the maximum label and the minimal label.The (p,1)-total number of a graph G,is the minimum span of a(p,1)-total labeling of G, denoted byλpT(G),andλpT(G)=min{k│G has a k-(p,1)-total labeling}.Havet and Yu studied the(p,1)-total labeling of G in[18],and gave a conjecture that:λpT(G)≤min{2Δ+p-1,Δ+2p-1}[r,s,t]-coloring of graph is the generalization of classical colorings.Definition 6 Given non-negative integers r,s,t,[r,s,t]-coloring of graph G is a mapping f,f:V(G)U E(G)→{0,1,…,k-1} such that:(1)for any uv∈E(G),│f(u)-f(v)│≥r;(2)for any uv,uw∈E(G),│f(uv)-f(uw)│≥s;(3)for any uv∈E(G),│f(u)-f(uv)│≥t.The[r,s,t卜chromatic numberχr,s,t(G)of G is defined to 6e the minimum k such that G admits an[r,s,t]-coloring.Obviously,f is a vertex coloring if r=1,s=t=0,an edge coloring if s=1,r=t= 0,a total coloring if r=s=t=1 and a(p,1)-total coloring if r=s=1,t=p.Unspecified symbols and terms see[20]and[21].In the first chapter of this paper,we mainly introduced some concepts,terminologies,s-ymbols and the development of adjacent vertex distinguishing coloring of graphs and two special total labeling of graphs.In the second chapter,we studied the adjacent vertex dis-tinguishing coloring of graphs and the T- adjacent vertex distinguishing edge(total) col-oring of Hamilton Graph.In the first part of the third chapter,we studied the(p,1)-total labeling,and gave a(p,1)一total labeling bound when p=3,Δ≥8,and also gave bounds on non-regular bipartite graph. In the second part,we studied the[r,s,t]-coloring of graph.We briefly summarize our main results as follows: Theorem2.1.5 If G is a simple graph,│V(G)│=ms+t,m is a positive integer,s,t are even,t≥m2s2+2ms-1,Δ(G)=ms+t-1,and the number of the maximal degree vertex of G is at least t,thenχ'as(G)=Δ(G)+2.Theorem2.1.6 If G is a simple graph,│V(G)│=ms+t,m is a positive integer,s is even,t is odd,t≥(m2s2)/2+(ms)/2,Δ(G)=ms+t-1,and the number of the maximal degree vertex of G is at least t,thenχ'as(G)=Δ(G)+2.Theorem2.1.7 If G is a simple graph,│V(G)│=ms+t,m is a positive integer,s is even,t is odd,t≥m2s2+2ms-2,Δ(G)=ms+t-1,and the number of the maximal degree vertex of G is at least t,thenχat(G)=Δ(G)+3.Theorem2.1.5-2.1.7 present three sufficient conditions of adjacent vertex distinguish-ing coloring conjecture affirms.Theorem2.2.6 If G is a non-regular Hamilton graph,then G exists a spanning tree T,such thatχ'Tas(G,T)≤Δ(G)+2;and for any spanning tree T of G,χTat(G,T)≤2Δ(G)+1.Theorem2.2.7 If G is a 3-regular Hamilton graph:then G exists a spanning tree T,such thatχ'Tas(G,T)=4；and for any spanning tree T of G,5≤χTat(G,T)≤6.Theorem2.2.8 If G is a k-regular Hamilton graph,k≥4,then G exists a span-ning tree T,such thatΔ(G)+1≤χ'Tas(G,T)≤Δ(G)+3；and exists a spanning tree T,such thatχTat(G,T)≤2Δ(G)+1.Theorem3.1.8 For any graph G,Δ(G)≥8,thenλ3T(G)≤2Δ(G)+1.Theorem3.1.13 For any non-regular bipartite graph G,Δ(G)=Δ,and the induced subgraph of maximal degree vertex of G contains K1,Δ-p+1,thenλpT(G)=Δ+p(3≤p). Theorem3.2.5 If G is a bipartite graph,r≥2χ'(G),thenχr,2,1(G)=χr,0,0(G)；If G is a non-bipartite graph,r≥(2χ'(G))/(χ(G)-2)+1 and r is odd,thenχr,2,1(G)=χr,0,0(G).For bipartite graph,the condition r≥2χ'(G) is best possible.Theorem3.2.6 IfΔ(G)≥2,s≥2r(r≥2),thenχr,s,1(G)=χ0,s,0(G).The condi-tion s≥2r(r≥2)is best possible.Theorem3.2.7 If G is a simple graph,χ'(G)=Δ(G)+1,and s≥r≥2,,thenχr,s,1(G)=χ0,s,0(G).The condition s≥r≥2 is best possible.Theorem3.2.8 If G is a simple graph,χ'(G)=Δ(G)+1,(?)≥max{r,t},t≠1, thenχr,s,t(G)=χ0,s,0(G).The condition (?)≥max{r,t},t≠1 is best possible.