Conditional Coloring And Defective Conditional Coloring Of Graphs

Graph theory is an important independent branch of the mathematics. For al-most30years, graph theory is most flourishing to develop. It shows strong vitality which young subjects have. Since the four color theorem was raised, it has been leading the development of graph theory. A lot of results emerged. Thus graph coloring problems are the focus of graph theory research. The graph coloring prob-lems have wide practical applications in many subjects, such as physics, biology, operations research, computer sciences, social sciences and so on. It is also play an important role in discrete mathematics. Many problems which are seemingly irrel-evant can be transformed into graph coloring problems. So T.R.Jensen and B.Toft claimed that graph coloring theory is at the central position in discrete mathemat-ics. And many classic coloring problems have been studied, such as face coloring, vertex coloring, edge coloring, total coloring and so on. Therefore, mathematicians proposed a lot of new coloring branches by adding various restrictions to the classic coloring problems.In2006, Lai Hongjian etc.introduced the r-conditional coloring of graphs in 《Discrete Mathematic《. In 《Conditional coloring of graphs》, they discussed the upper bound of r-conditional chromatic number of general graphs, the r-conditional chromatic number of several special graph classes and several sufficient and nec-essary conditions of normal graphs etc. In2012, Sun Lei, Liu Ting introduced defective conditional coloring. In Liu Ting’s graduation thesis, she studied defec-tive r-conditional coloring of some special graphs. In this paper, I will continue to study conditional coloring and defective conditional colorings problem. In the first chapter of this paper, we mainly introduced some concepts, termi-nologies, symbols and the history and the development of coloring problems. We follow the terminology and notations of.Definition1For an integer k>0, let k={1,2,…, k}. A proper k-coloring of a graph G is a map c:V(G)â†'k such that if u, v∈V(G) are adjacent vertices in G, then c(u)≠c(v). The smallest k such that G has a proper k-coloring is the chromatic number of G, denoted by X(G).Definition2For integers k>0and r>0, a proper (k,r)-coloring of a graph G is a map c:V(G)â†'k satisfying both the following:(C1) c(u)≠c(v) for every edge uv∈E(G); and(C2)|c(NG(v))|≥min{|NG(v)|,r} for any v∈V(G).For a fixed number r>0, the r-conditional chromatic number of G, denoted by Xr(G), is the smallest k such that G has a (k, r)-coloring.The r-conditional coloring problem is a coloring problem with a condition on neighborhood. By the definition of Xr(G), it follows immediately that X(G) X1(G).Definition3Defined a graph G as normal if X2(G)=x(G).For r≥3, we can similarly define that a graph G is r-normal if Xr(G)=X(C).In the second chapter of this paper, we studied r-conditional coloring of graph-s. We gave two sufficient conditions of r-normal graphs. We also discussed the3-conditional chromatic number and the r-conditional chromatic number of several special graph classes.Theorem2.1.12Let G a simple graph, if α(G)=α,â–³(G)≤[n-rα/α-1]-1, then G is r-normal.Theorem2.1.13Except one pair of adjacent vertex x1y1, for any x, y∈V(G), and xy∈E(G),if d(x)+d(y)≥n+2,then G is a3-normal graph.Theorem2.1.14Let G 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)except one group of r vertices,then G is r-normal.Theorem2.2.2Let G a outerplanar graph,δ(G)=2,then X3(G)≤6.Definition4Let G is a plane graph with maximum degreeâ–³(G)|V(G)|-k,k=1,2…,then G is a hk-grapy.A hk-grapy(k=1,2)is a high-degree plane graphBased on the definition of high-degree plane graph,we gave two upper bounds of3-conditional chromatic number of high-degree plane graph with some restric-tions.Theorem2.2.8Let G is a h1-graph,|V(G)|≥2,then X3(G)≤6.Theorem2.2.9Let G is a h2-graph,if|V(G)|≥9and there are two vertices such that d(W1)=d(W2)=â–³(G),w1w2∈E(G),then X3(G)≤5.Definition5Let G is a simple graph,V(G)={v1,v2,…vn),join m ver-tices vjo∈G(jo∈{1,2,…,n))into a cycle,we shall denote the new graph by Cm. G(ujo),simply by G*,Gi(i=1,2,…,m)is a copy graph of G.The vertex set and edge set of G*are following: Theorem2.3.2If n≥3, r≥2, thenDefinition6A defective (k, d)*-coloring of a graph G is an integer as-signment c:V(G)â†'k such that:each vertex v∈V(G) is adjacent to at most d vertices of the same color.The smallest k such that G has a defective (k,d)*-coloring is the defective chromatic number of G.Let G is a simple graph,v∈V(G),w∈NG(v) and c is a coloring of G. If c(v)=c(ω), then v is called a bad vertex. Defective coloring allow that there are at most d bad vertices among adjacent vertex set of any vertex. By the definition of the defective chromatic number, it follows immediately that a defective (k,0)*-coloring of G is also a proper k-coloring of G.Definition7For integers k>0, r>0, s≥0, A defective (r,s)-conditional coloring of a graph G is an integer assignment c:V(G)â†'k, such that:(1) there are at most s vertices v1,v2,……,vs∈N(v) such that c(v1)=c(v2)=..=c(vs)=c(v),for (?)v∈V(G);(2)|c(N(v))|≥min{|N(v)|,r}, for V∈V(G).For fixed numbers r>0, s≥0, the defective (r, s)-conditional chromatic number of G, denoted by X(r,s)(G), is the smallest k such that G has a defective (r, s)-conditional coloring.The defective (r, s)-conditional coloring problem is a coloring problem with a condition on neighborhood. By the definition of X{r,s)(G), it follows immediately that a defective (1, s)-conditional coloring of G is also a defective (k, s)*-coloring of G, a defective (r,0)-conditional coloring of G is also a r-conditional coloring of G, and a defective (1,0)-conditional coloring of G is also a proper k-coloring of G.In the third chapter of this paper, we studied defective (r, s)-conditional color- ing of graphs.We gave a upper bound of the defective(r,s)-conditional chromatic number of special graph classes.We also discussed the defective(r,s)-conditional chromatic number of several special graph classes.Theorem3.1.5If G is a connected graph,T is a spanning tree of G,G0=G\E(T),then X(Ï„,s)(G)≤X(Ï„,s)(T)+X(Ï„,s)(G0),r≥2,s≥1.Theorem3.1.6If r≥2,s≥1,then X(Ï„,s)(G)≤△2-â–³.Definition8Let G is a simple graph with the vertex set V(G)={v1,v2,…,vn), I2is an independent set of two vertices.Let G[I2] denote the graph obt ained from G by replacing each vertex by the two vertices of the independent set I2.The vertex set and edge set of G[I2] are following:V(G[I2])={v1,v2,…,vn,v’1,v’2,…,v’n), E(G[I2])=E(G)∪{v’iv’j,v’iv’j|vivj∈E(G)}.G[I2]is the split graph of G.Theorem3.2.2If n,s≥1,I2is an independent set of two vertices,then...