Several N(p,q) Labelling Problems Of Graphs And Two Coloring Problems Of Graphs

The labelling problem of graphs is an important problem of graph theory.It mainlydoes research on kinds of partition problems of graphs,and these problems all have wideapplication background.One of them is based on the background of the channel assign-ment problem. The higher sensitive basic channel assignment problems require that thetransmitters which interfer each other obtain diferent channels,the diference of channelswhich interfer a transimitter can’t be too small. Transfering it into the problem of graphtheory is that it asks the adjacent vertices to obtain diferent labels and the labels of theveitices which are adjacent to a vertex should have some interval.Basic on this,Griggsand Yeh put forward the famous L（2,1）-labeling problem in1992; Sun lei put forwardthe labelling with condition on neiborhood.Definition1[22]For positive integer k,a k L1,2labelling of graph G is a mappingc: V （G）â†'{1,2,, k}, such that:（1）If uv∈E（G）,then c（u）=c（v）;（2） u, v∈V （G）,if w∈V （G）,such that u, v∈NG（w）,then|c（u） c（v）|≥2.The smallest k such that G has a k L1,2labelling is called the labelling numberwith condition on neiborhood of G,denoted L1,2（G）.Based on the previous researches,this paper presents two labelling problems whichcan be applied to channel assignment problems, they are semi-total neiborhood restric-tion labelling SN （p, q） and total neiborhood restriction labelling T N （p, q）. SN （p, q）labelling requires that the adjacent vertices obtain diferent labels and the diference of labels of the vertices which are neighbors of a vertex whose degree is no less than acertain positive integer p is at least q. That is,the adjacent transmitters get diferentchannels,and as the number of channels which interfer a transmitter to p, the diferenceof the channels is at least q. T N （p, q） labelling requires not only the adjacent verticesobtain diferent labels and the diference of labels of the vertices which are neighbors ofa vertex whose degree is no less than a certain positive integer p is at least q,but alsoasks the diference of labels of the vertices which are neighbors of a vertex whose degreeis less than the positive integer p is at least1.In other words, based on the requirmentof SN （p, q） labelling,T N （p, q） labelling also requires that the diference of the channelsis at least1when the number of channels which interfer a transmitter is less than p.Thedefinitions as follows:Definition2For positive integers k, p, q,q≥2,a k N （p, q） labelling of graph Gis a mapping c: V （G）â†'{1,2,, k}, such that:（1） For u, v∈V （G）, if d（u, v）=1, then|c（u） c（v）|≥1;（2） If w∈V （G）, and d（w）≥p,then for u, v∈NG（w）,|c（u） c（v）|≥q.The labelling of G which meets （1）（2） is called semi-total neiborhood restrictionslabelling SN （p, q）. The smallest k such that G has a SN （p, q） labelling is called semi-total neiborhood restrictions labelling number,denoted SLp,q（G）.（3） d（w）<p, u, v∈NG（w）,|c（u） c（v）|≥1.The labelling of G which meets （1）（2）（3） is called total neiborhood restrictions la-belling T N （p, q）. The smallest k such that G has a T N （p, q） labelling is called totalneiborhood restrictions labelling number,denoted T Lp,q（G）.Easy to see that if p=, q=2,then T Lp,q（G）=L1,2（G）.The coloring problem of graph is also an important part in the field of graph theory.And the mathematicians put forward kinds of coloring problems and has studied manyclassical coloring problems such as face coloring, vertex coloring, edge coloring and totalcoloring. As the constantly developing of graph coloring problems,Mathematicians pro-posed a lot of new branchs of coloring problems of graphs which based on the classicalcoloring problems. The conditional coloring of graphs is a new branch which was intro- duced by Lai Hongjian ect.in2006.Definition3[15]For positive integers k and r,a conditional （k, r） coloring of graphG is a mapping c: V （G）â†'{1,2,, k}, such that:（1）If uv∈E（G）,then c（u）=c（v）;（2）For v∈V （G）,|c（NG（v））|≥min{|NG（v）|, r}.For a fix number r,the smallest k such that G has a proper k coloring is the con-ditional chromatic number of G,denoted χr（G）.The injective coloring problem of graph is also an important coloring problems.Ainjective coloring problem of graph is a coloring which requairs the neighbors of a vertexof graph get diferent colors.We mainly introduced some symbols and terminologies and the coloring problemsof graphs and labelling problems of graphs in the first chapter.In the second chapter,we mainly studied SN （p, q） labelling problem and T N （p, q） labelling problem of somegraphs,and presented some results.In the first part of the third chapter, we introduced thedevelopment of conditional coloring and got a new result;in the second part we studiedthe proper injective coloring of some special graphs.This paper mainly gets the followingresults.Theorem2.2.2If a graph is a complete graph Kn,then T Lp,q（Kn）=SLp,q（Kn）=（n1）q.Theorem2.2.3If a graph is a bipartite graph K_m,n,m≤n, n≥p, then（1） If m=n,then SLp,q(K_m,n)=T Lp,q(K_m,n)=（n1）q+1.（2） If m <n,then SLp,q(K_m,n)=T Lp,q(K_m,n)=（n1）q.Theorem2.2.5If G only has a vertex v with degree no less than p, and|V （G）|=n, dG（v）=, then（1）（a） If （1）q≥n1,then T Lp,q（G）=（1）q;（b） If （1）q <n1,then T Lp,q（G）≤n1. （2）（a） If （1）q≥2,then SL_p,q（G）=（1）q;（b） If （1）q <2,then SL_p,q（G）≤2.Theorem2.2.6If G only has two adjacent vertices u, v with degrees no less thanp, and d（u）=d（v）=s,|V （G）|=n. u, v don’t have the same adjcent vertex, the verticesin NG[u] and NG[v] except u, v aren’t adjacent,then（1） If q（s1）≥n2,then T L_p,q（G）=SL_p,q（G）=（s1）q+1;（2） If q（s1）<n2,then T L_p,q（G）≤n1;（a） If （s1）（q2）≥s,then SL_p,q（G）=（s1）q+1;（b） If （s1）（q2）<s,then SL_p,q（G）≤3s1.Theorem2.2.7If G only has two adjacent vertices u, v with degrees no less thanp, and d（u）=d（v）=s,|V （G）|=n. u, v have m same adjcent vertices, the verticesin NG（u） and NG（v） except the m same adjcent vertices aren’t adjacent,then（1） If （s1）（q1）≥n+m2s, then T L_p,q（G）=SL_p,q（G）=（s1）q+1;（2） If （s1）（q1）<n+m2s, then T L_p,q（G）≤n s+m;（a） If （s1）（q1）≥s,then SL_p,q（G）=（s1）q+1;（b） If （s1）（q1）<s,then SL_p,q（G）≤2s.Theorem2.2.8If G only has two adjacent vertices u, v with degrees no less thanp, and|V （G）|=n, d（u）=s, d（v）=t, s> t.u, v have m same adjcent vertices, thevertices in NG（u） and NG（v） except the m same adjcent vertices aren’t adjacent,then（1） If （s1）q≥n+m t,then T L_p,q（G）=SL_p,q（G）=（s1）q;（2） If （s1）q <n+m t,then T L_p,q（G）≤n t+m;（a）If （s1）q≥t+s,then SL_p,q（G）=（s1）q;（b）If （s1）q <t+s,then SL_p,q（G）≤t+s.Theorem2.2.9If G only has two adjacent vertices u, v with degrees no less thanp, and d（u）=s, d（v）=t, s> t,|V （G）|=n. u, v don’t have same adjcent vertex, thevertices in NG[u] and NG[v] except u, v aren’t adjacent,then（1） If （s1）q≥n1,then T L_p,q（G）=SL_p,q（G）=（s1）q; （2） If （s1）q <n1,then T Lp,q（G）≤n1;（a） If （s1）（q1）≥2t,then SLp,q（G）=（s1）q;（b） If （s1）（q1）<2t,then SLp,q（G）≤2t+s1.Theorem2.2.10If G only has two vertices u, v with degrees no less than p, u, vhave m same adjcent vertices, the vertices in NG[u] and NG[v] except the m same adjcentvertices aren’t adjacent,|V （G）|=n, d（u）=s, d（v）=t, s≥t,then（1） If （s1）q≥n t+m1,then T Lp,q（G）=SLp,q（G）=（s1）q;（2） If （s1）q <n t+m1,then T Lp,q（G）≤n t+m1;（a） If （s1）（q1）≥t+2,then SLp,q（G）=（s1）q;（b） If （s1）（q1）<t+2,then SLp,q（G）≤t+s+1.Theorem2.2.11If G only has two vertices u, v with degrees no less than p,|V （G）|=n, d（u）=s, d（v）=t, s≥t, u, v don’t have same adjcent vertex,and the vertices in NG[u]and NG[v] except u, v aren’t adjacent,d（u, v）>3, then（1） If （s1）q+t≥n1,then T Lp,q（G）=SLp,q（G）=（s1）q;（2） If （s1）q+t <n1,then T Lp,q（G）≤n t1;（a） If （s1）q≥s+t+1, then SLp,q（G）=（s1）q;（b） If （s1）q <s+t+1,then SLp,q（G）≤t+s+1.Theorem3.1.9If G is a connected graph with only one maximum degree vertex v,the maximum degree of V （G）\{v} is t,0<t≤/21,（G）≥3,then χr（G）≤（t）2.Theorem3.2.5If G is a connected graph with only one maximum degree vertexv, d（v）=, T=G {v} is a tree,and there are p vertices with degree1in NG（v）,m=u∈mVa （xT）|NG（v） NT[u]|,then χi（G）≤2p m+1.Corollary3.2.6If G has a vertex v, d（v）=t≤, T=G {v} is a tree,andthere are p vertices with degree1in NG（v）, m=u∈mVa （xT）|NG（v） NT[u]|,then χi（G）≤+t p m+2. Theorem3.2.7If G is a connected graph,there are two disadjacent vertices u0, v0such that G {u0, v0}=T is a tree,|NG（u0） NG（v0）|=n2,（G）=, s=u∈mVa （xT）|NT[u] NG（u0）|, t=v∈mVa （xT）|NT[v](NG（v0）|,|V （G）|=n,thenTheorem3.2.8If G is a connected graph,there are two disadjacent vertices u0, v0such that G {u0, v0}=T is a tree, m=|NG（u0） NG（v0）|<n2,（G）=, s=u∈mVa （xT）|NT[u] NG（u0）|, t=v∈mVa （xT）|NT[v](NG（v0）|,|V （G）|=n,thenCorollary3.2.9G is a connected graph,and G has two adjacent vertices u0, v0such that G {u0, v0}=T is a tree, m=|NG（u0） NG（v0）|,（G）=, s=u∈mVa （xT）|NT[u] NG（u0）|, t=v∈mVa （xT）|NT[v](NG（v0）|,|V （G）|=n,thenχi（G）≤+m sTheorem3.2.11G is a connected graph,and G has two adjacent vertices u0, v0such that G {u0, v0}=Km,n=（X, Y）,m≥n≥2,andmax{d（u0）, d（v0）}<n, NG（u0） X,thenTheorem3.2.12G is a connected graph,and G has two adjacent vertices u0, v0such that G {u0, v0}=Km,n=（X, Y）,m≥n≥2,and max{d（u0）, d（v0）}<n, NG（u0） Theorem3.2.13G is a connected graph,Km,nis the spanning subgraph of G,G0=G\E（Km,n）, m≥n≥2,then χi（G）≤m+n.Theorem3.2.15G is a connected graph,T is a spanning tree of G, G0=G\E（T）,（T）=（G）.（1）If G0is a set of m matching edges,m1edges of these m edges are incident withthe vertices with distance2on the tree,then χi（G）≤+1+m m1.（2） If G0is a path with leghth l, then...