Conditional Coloring And Defective Conditional Coloring Of Graphs

Graph theory is an important branch of the mathematics. It is a young butrapidly maturing subject. Graph coloring problem is one of the important problemswith good value in theory and extensively practical significance. It is also play animportant role in discrete mathematics. Many problems which are seemingly irrel-evant can be transformed into graph coloring problems. So T.R.Jensen and B.Toftclaimed that graph coloring theory is at the central position in discrete mathe-matics. What’s more, The graph coloring problem also have strong applicationbackground. It has a wide range of application in the optimization, the computertheory, network design and other fields. Then, all kinds of coloring problems are putforward successively by mathematicians. And many classic coloring problems havebeen studied, such as face coloring, vertex coloring, edge coloring, total coloringand so on.Therefore, mathematicians proposed a lot of new coloring problems thatbased on 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 theupper bound of r-conditional chromatic number of general graphs, the r-conditionalchromatic number of several special graph classes and several sufcient and nec-essary conditions of normal graphs etc. In1969, Chartrand, Geller, Hedetniemiintroduced the improper coloring of graphs. With more and more mathematiciansstudying this problem, a lot of beautiful results also have been put forward, forexample, Cowen,Cowen, and Woodall investigated defective chromatic number ofouterplanar and planar graphs in<Defective Colorings of Graphs in Surfaces: Parti-tions into Subgraphs of Bounded Valency>. Based on the previous researches, this paper presents defective r-conditional coloring, which integrates the r-conditionalcoloring with defective coloring. This coloring problem is also a coloring problemwith a condition on neighborhood.We only consider the simple connected graph G.In the first chapter of this paper, we mainly introduced some concepts, ter-minologies, symbols and the development of coloring problems. We follow theterminology and notations of [1].Definition1[1]For an integer k>0, let k={1,2,, k}. A proper k-coloringof a graph G is a map c: V （G）â†'k such that if u, v∈V （G） are adjacent verticesin G, then c（u）=c（v）. The smallest k such that G has a proper k-coloring is thechromatic number of G, denoted by χ（G）.Definition2[7]For integers k>0and r>0, a proper （k, r）-coloring of agraph 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, denotedby χr（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 onneighborhood. By the definition of χr（G）, it follows immediately that χ（G）=χ1（G）, and so r-conditional coloring is a generalization of the classical graph col-oring. In a certain sense, it describes a normal coloring with uniform characteristics.Definition3[7]Defined a graph G as normal if χ2（G）=χ（G）. For r≥3, wecan similarly define that a graph G is r-normal if χr（G）=χ（G）.In the second chapter of this paper, we studied r-conditional coloring of graphs.We gave some sufcient conditions of3-normal graphs. We also discussed the3-conditional chromatic number of several special graph classes. Theorem2.1.13For any x, y∈V （G）, and xy∈E（G）, if d（x）+d（y）≥n+2,and G does not contain an even cycle without a chord as an induced subgraph, thenG is a3-normal graph.Theorem Definition4[22]Let 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 obtainedfrom G by replacing each vertex by the two vertices of the independent set I2. Thevertex set and edge set of G[I2] are following: V （G[I2]）={v1, v2,, vn, v′ivj|vivj∈E（G）}. G[I2] is the split graph of G.The3-conditional chromatic numbers of the split graphs of some special graphswere given. We defined a new graph according to Wn, the3-conditional chromaticnumbers of the new graph was given.Definition5[29]Given m （m≥3） graphs G0, G1,, Gm1, for i=0,1,, m1, let ei=vivi+1∈Gi. Let cm=c0c1cm1be a cycle of length m, construct anew graph as following:（1） Delete the edges ei, for i=0,1,, m1;（2） Identify all the viinto a single vertex and name x; （3） Identify vi+1and ci, for i=0,1,, m1（the addition of i+1modulom）.We shall denote the resulting graph by S（G0, e0, G1, e1,, Gm1, em1）, sim-ply by S.If given m（m≥3） graphs Gi=Kni,（i=1,2,, m）, then S（G0, e0, G1, e1,,Gm1, em1）=S（Kn1, e1, Kn2, e2,, Knm, em）, simply by S1, The vertex x is de-noted by v0, and the vertex identified by vi+1and cidenoted by v1, v2,, vm; theother vertices of Knicorresponding to viare denoted by vi1, vi2,, vi（ni2）, i=1,2,, m. S1is the generalized haj′os sum of Kn.Theorem2.2.19S1is said as we just defined, then N1≤χ3（S1）≤max{6, N}, N=max{ni|1≤i≤m}.Theorem2.2.20If n≥5, then χ₃(S₁, if there is ni=ni+1=N;1modulo m,1≤i <j≤m N1, others.i+, n=min{ni|1≤i≤m}, N=max{ni|1≤i≤m}.Corollary2.2.21When n≥5, then χ3（S1）=χ（S1）.Theorem2.2.23Let G be a simple graph,≤3. If every two adjacent3-vertices are in a triangle, then χ3（G）≤6.Definition6[5]A 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 dvertices of the same color.The smallest k such that G has a defective （k, d）-coloring is the defectivechromatic number of G.By the definition of the defective chromatic number, it follows immediatelythat 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）-conditionalcoloring 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 chromaticnumber of G, denoted by χ（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 acondition on neighborhood. By the definition of χ（r,s）（G）, it follows immediatelythat a defective （1, s）-conditional coloring of G is also a defective （k, s）-coloring ofG, 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 the defective （r, s）-conditional chromatic number of specialgraph classes. We also discussed the defective （3,1）-conditional chromatic numberof several special graph classes.Theorem3.1.3If G is a tree and|V （G）|≥3, r≥2, s≥1, thenχ（r,s）（G）=min{r,（G）}.Theorem3.1.4If m≥n≥2, r≥2, s≥1, thenTheorem3.1.5If n≥3, r≥2, s≥1are integers, thenTheorem3.2.1If Wn（n≥4） is a wheel, then χ（3,1）（Wn）=4. Theorem3.2.2If F_n（n≥4） is a fan, then χ（3,1）（Fn）=4.