Improper Coloring Of Planar Graph

Let G= （V, E） be a simple planar graph and C₁, C₂,..., c_k be k non-negative integers. A graph G is （c₁, c₂,..., C_k）-colorable if the vertex set can be partitioned into k sets V₁, V₂,..., V_k such that for every i,1≤i≤k, the subgraph G[Vi] has maximum degree at most Ci.Study of graph coloring problems comes from the famous four-color problem has always been a hot sector of graph theory is also difficult. It is well-known that the problem of deciding whether a planar graph is properly 3-colorable is NP-complete. In 1959, Grotzsch showed the famous theorem that every triangle-free planar graph is 3-colorable. Triangle is allowed so many scholars working on a sufficient condition for Planar graph is 3-colorable. In 1976, Steinberg raised the famous conjecture that every planar graph without cycles of length 4 or 5 are （0,0,0）-colorable. In this paper, we prove that every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is （1,1,0）-colorable, which improves the result of Xu and Wang, who proved that every planar graph without cycles of length 4 or 6 is （1,1, 0）-colorable.● In chapter 1, we introduce the background of the research and the problem we will solve.● In chapter 2, we introduce some necessary basic concepts and symbols.● In chapter 3, we give some reducible configurations of G.● In chapter 4, we give the discharging rules.● In chapter 5, we give the proof of the final charge of vertex and faces in G.