Three Colouring Problems Of Graphs With A Condition On Neighborhood

Because of the importance of graph theory in mordern applied mathematics,in particular,the development of computer science and combinatorial optimization,Graph theory,as an independent subject in mathematics,has experienced explosive develop-ment. Coloring problems are active research fields in graph theory with good value in theory and practical significance.Therefore,mathematicians proposed a lot of new color-ing problems that based on the classic coloring problems such as vertex coloring and edge coloring.In 2006, Lai Hongjian etc. introduced the conditional coloring of graphs in<>.In "Conditional coloring of graphs",they discussed the conditional chro-matic numbers of several special graph classes, upper bound of conditional chromatic number of general graphs and several sufficient and neccessary conditions of normal graphs ect.In 2006, G.Hahn,J.Kratochvil,J.Siran,D.Sottean ect. published" On the injec-tive chromatic number of graphs" in《Discrete Mathrmatie》.They firstly introduced the injective coloring of graphs.Since then,on this coloring problem, especially on planar graph with a certain condition, emerged a lot of good results.In 2008,Sun Lei,Liu Xiaoxiao introduced the lablelling with a condition on neighborhood.In Liu Xiaoxiao'graduation thesis, she studied the lower bound of the labelling numbers of graphs with some certain conditions. The lablelling numbers with a condition on neighborhood of cycles and trees, several properties of the lablelling with a condition on neighborhood ect. These three coloring problems are all coloring problems with a condition on neighborhood. In the first chapter of this paper,we mainly introduced some concepts,terminologies,symbols and the development of coloring problems.We follow the terminology and notations of [1].Definition 1 A proper k-coloring of a graph G is an integer assignment c to the vertex set V(G) such that the colors of any adjacent vertics in G are different.The smallest k such that G has a proper k-coloring is the chromatic number of G,denoted byχ(G).In this paper, the coloring without special illustration is proper coloring.Definition 2 A conditional (k,r)-coloring of a graph is a proper k-coloring of the vertices of G such that both of the following hold:(1)if uv∈E(G),then c(u)≠c(v);(2)for any v∈V(G),│c(NG(v))│>min{NG(v)│,r}.'For a fix number r>0, the smallest k such that G has a proper (k,r)-coloring is the rth order conditional chromatic number of G,denotedχt(G).Definition 3 A graph G is normal ifχ2(G)=χ(G).Similarly,a graph G is r-normal ifχr(G)=χ(G).In the second chapter, we studied conditional coloring of graphs.we gave some suffi-cient and neccessary conditions or sufficient conditions of normal graphs and r-normal graphs. Also,we improved the upper bound of the conditional chromatic numbers.Theorem 2.1.5 Let n=│V(G)│> 3.Ifδ(G)>[n/2]then G is normal.This bound onδ(G) is best possible.Theorem 2.1.7 Let n=|V(G)|.If the degree sum of any two adjacent vertices of G is larger than n,then G is normal.This bound on degree sum is best possible.Theorem 2.1.9 If any vertice of G with degree larger than 1 is contained in triangles,then L(G),as the liner graph of G,is normal.Also,the liner graph of Cn with n≡1(mod2)and n≡0(mod3)is normal.Theorem 2.2.2 Let G be a graph with n=V|G| and let r≥2be an integer.Ifδ(G)≥[(r-1)n/r]+1,then G is r-normal.The lower bound onδ(G)is best possible.Theorem 2.2.3 Let G be a connected graph with n vertices.If the degree sum of any r vertices whose induced subgraph is connected is larger than n(r-1),then G is r-normal.This bound on degee sum is best possible.In[8]Ding Chao,Fan Suohai,Lai Hongjian studied the upper bound of conditional chromatic number of graphs and gave the result thatχr(G)≤△2+1,here equality hold if and only if G is a Moore graph.Theorem 2.3.4 If G is C5-free and△(G)≥2,thenχr(G)≤△2.Definition 4 A graph is injective if its restricition to the neighbourhood of any vertices injective.That is if x,y∈V(G) have a common neighbor in G then c(x)≠c(y).The smallest k such that G has a injective coloring is the injective chromatic number.In the third chapter,we studied injective coloring of graphs.we gave some special concepts,notions that used in planar graphs and some present results.Also,let g≥6,we gave the upper bound of injective chromatic numbers and special properties of injective chromatic number of graphs when△=8 or△=9.Theorem 3.2.5 Let G be a planar graph with g(G)≥6 and△(G)=△,(1)χi(G)≤△+2；(2)ifχi(G)≤△+1 when△=8,then for any G,χi(G)≤△(G)+1；(1)ifχi(G)=△when△=9,then for any G,χi(G)=△(G).Definition 5 A k-L1,2-labelling of graph G is defined as a function c V(G)→>{0,1,2…,k} such that both of the following hold:(1) If uv∈E(G),then c(u)≠c(v);(2) If there is a vertex w such that u, v∈NG(w),then |c(u)-c(v)|≥2.The lablelling numbers with a condition on neighborhood of G,denoted by L1,2(G), is the smallest number k such that G has a k-L1,2-labelling.In the forth chapter, we studied the lablelling with a condition on neighborhood of graphs.We gave the sufficent and neccessary conditions or sufficent conditions when L1,2(G) reach the upper bound or lower bound. We also gave the upper bound of the lablelling numbers with a condition on neighborhood of G(G≠K2) and the lablelling numbers with a condition on neighborhood of special graphs.Theorem 4.1.2 L1,2(G)=2(n-1)(n=|V(G)|)if and only if G is a compelete graph or G has diameter 2 and every edge of G is contained in a triangle.Theorem 4.1.3 L1,2(G)=2(△-1)(△=△(G)),then the following hold:(1) any two maximum degree vertices are not adjacent,(2) there are at least 2 vertices in the neighbourhood of the maximum degree ver-tices that not adjacent to other vertices,(3) if two maximum degree vertices are adjacent and their neighbourhood are the same,then there are at least 3 vertices in the neighbourhood that not adjacent to each other.Theorem 4.1.5 If G≠K2,then L1,2(G)≤2△2-2△.This bound is best possible with the condition.G is a simple graph.The first subdivision S1(G) of G is the graph formed by sub-dividing each edge of G once.That is each edge of G is replaced by a path of length 2.Let G= (V(G),E(G)),V(G)={v1,v2,…,vn},Mycielskian graphM(G),of G,the set of vertices and the set of edges are defined as follow:V(M(G))={v1,v2,v3,…vn,u1,u2,u3,…,un,v}, E(M(G))=E(G)∪{uiv│i=1,2…,n}∪{uivj│vivj∈E(G)}.Theorem 4.2.2 Let n=│V(G)│,G is not a complete graph,△(G)=△,S1(G)is the first sub division of G,then 2(△-1)≤L1,2(S1(G))≤2△-1.If G is a complete graph,then L1,2(S1(G))=2△.Theorem 4.2.4 Let n=│V(G)│,△(G)=△≤(?).M(G)is the Myciel-skian graph of G,then L1,2(M(G))=2(n-1).It is the trivial lower bound of the lablelling numbers with a condition on neighborhood of G.