| Graph theory is an important branch of the mathematics.It is a young but rapidlymaturing subject. Graph coloring problem is one of the important problems with goodvalue in theory and practical significance.The frequency assignment problem is that of assigning a frequency to each radiotransmitter so that interfering transmitters are assigned frequencies whose separation isnot in a set of disallowed separations.In the channel assignment problem,we want to assignchannels on each transmitter.If two transmitters are close,then they must receive diferentchannels:if two stations are too close,the separation of the channels assigned to them hasto be at least two;moreover,if the distance between two stations is two,then they mustreceive diferent channels. Regarding this kind of situation,the L（2,1） labelling problemwas produced by Griggs and Yeh[19] in1992.In2000,G.J.Chang[10]etc generallized thisproblem to the L（p,1） labelling.We only consider the simple connected graph G.Definition1[10]The L（p,1） labelling of a graph G is a mapping L from the vertexset V （G） to the integer set: V （G）→{0,1,, k},such that:（1） for any u, v∈V （G）,|L（u） L（v）|≥p,if d（u, v）=1;（2） for any u, v∈V （G）,|L（u） L（v）|≥1,if d（u, v）=2.Whittlesey studied the L（p,1） labelling of the first subdivision of a graph G. Thefirst subdivision of a graph,the graph s1（G） obtained from G by inserting one vertex alongeach edge of G.An L（p,1） labelling of s1（G） corresponds to a special total coloring ofG.This coloring,which is introduced by Havet and Yu[7],is called （p,1） total labelling. Definition2λpT[7]The （p,1） total labelling of a graph G is a mapping c: V （G） E（G）→{0,1,2,, k},such that:（1） for any u, v∈V （G）,|c（u） c（v）|≥1,if uv∈E（G）;（2） for any u, v, w∈V （G）,|c（uv） c（uw）|≥1,if uv, uw∈E（G）;（3） for any u, v∈V （G）,|c（u） c（uv）|≥p,if uv∈E（G）.The span of a （p,1） total labelling is the diference between the maximal label andthe minimal label.The （p,1） total number of a graph G is the minimum span of a （p,1） total la-belling of G,denoted λpT（G）.Fredeic Havet and Min-Lin Yu[7] provided the general lower and upper bounds forλpT（G）.And they introduced the well-known （p,1） Total Labelling Conjecture,that is:λpT（G）≤min{（G）+2p1,2（G）+p1}.It was also shown that λpT（G）≤2（G）+p1for any graph G.[r, s, t]-coloring of a graph G is the generalization of classical total coloring.Definition3[1]Given non-negative intergers r, s, t,[r, s, t] coloring of a graph G isa mapping c: V （G） E（G）→{0,1,2,, k1},such that:（1） for any two adjacent vertices vi, vj,having|c（vi） c（vj）|≥r;（2） for any two adjacent edges ei, ej,having|c（ei） c（ej）|≥s;（3） for a vertex viand its incident edge ej,having|c（vi） c（ej）|≥t.The [r, s, t] chromatic number χr,s,t（G） is defined to be the minimum k such thatG admits an [r, s, t] coloring.Obviously c is a vertex coloring if r=1, s=t=0,an edge coloring if r=t=0, s=1,a total coloring if r=s=t=1and a （p,1） total coloring if r=s=1, t=p.In2007,Hajo Broersma[11] varied the classic vertex coloring and put some restric-tions on the backbone of G. The new kind coloring was called BackBone coloring.Herewe will continue to use this thought limiting the conditions of [r, s, t] coloring on thespanning tree of the graph.Let G be a graph,it has a spanning tree T,so we had definitionas follows: Definition4Let G be a simple connected graph,k is a positive integer,c is a normaltotal coloring of G: V （G） E（G）→{0,1,2,, k1},T is a spanning tree of G,r, s, tare non-negative integers.If（1） for any u, v∈V （G）,if dT（u, v）=1,then|c（u） c（v）|≥r;（2） for any uv, uw∈E（T）,having|c（uv） c（uw）|≥s;（3） for any u∈V （G）, uv∈E（T）,having|c（u） c（uv）|≥tc is defined to be an [r, s, t] T total coloring of G.χrT,sT,tT（G, T） is defined to be the minimum k such that G admits an [r, s, t] T total coloring.We briefly summarize our main results as follows:Theorem2.1.13If G is a bipartite graph and r≥s（χ′（G）1）+2,then χr,s,1（G）=χr,0,0（G）; if G is a non-bipartite graph and r≥sχ′（G）χ（G） s+1and r is not a multiple ofs,then χr,s,1（G）=χr,0,0（G）.The lower bound of the bipartite graph in the theorem is sharp.Theorem2.1.14When （G）≥2, χ′（G）=（G）,and s≥2r, r≥2t,then χr,s,t（G）=χ0,s,0（G）.Theorem2.1.15When χ′（G）=（G）+1,and s t≥r≥t,then χr,s,t（G）=χ0,s,0（G）.Theorem2.2.16For any graph G,when （G）≥6, then λ3T（G）≤2（G）+1.Theorem2.2.17For any simple graph G,（G） is the maximum degree of G,if（G） is even and at least6, then λ2T（G）≤2（G）-1.Theorem3.1.2For any simple connected graph G, is the maximum degree ofG,T is an arbitrary spanning tree of G, then χrT,1T,1T（G, T）≤2+2r. Theorem3.1.3For any simple connected graph G, is the maximum degree ofG,T is an arbitrary spanning tree of G, If s≥（△-1）△,then χrT,sT,1T（G, T）≤（2s+1）△-2s+2r+2.Theorem3.2.1Given a simple connected graph G, is the maximum degree ofG.If there is a spanning tree T0of G,and the vertices whose degree is1in T0are not thevertices of maximum degree of G, then χrT0,1T0,1T0（G, T0）≤2+2r1.If G=（V （G）, E（G）） is a simple graph,V （G）={v1, v2,, vn},The vertex set andedge set of G are defined as follows:V （G′）={v1, v2,, va, v1, v2,, vn},E（G′）={v′ivj, vivj, viv′j, vivj|vivj∈E（G）},then G′is defined vertex splited graph of graph G.Theorem3.2.2When G′is the vertex splited graph of the connected graph G,and（G）=, then there is a spanning tree T′of G such that χr′T′,1T′,1T′（G, T′）≤4+2r. |
