Improper Coloring Of Graphs

All graphs considered in this paper are simple planar graphs. A graph G is called improperly(d1, d2,…,dk)-colorable, or simply (d1,d2,…, dk)-colorable, if the ver-tex set of G can be partitioned into subsets V1, V2,…,Vk such that the graph G[Vi] induced by Vi has maximum degree at most di for1≤i≤k. This notion gener-alizes those of proper k-coloring(when d1=d2=…=dk=0) and d-improper k-coloring(when d1=d2=…-dk=d≥1).Improper coloring was introduced almost simultaneously by Burr and Jacobson, Harary and Jones and Cowen, Cowen and Woodall. The notion of list improper coloring was introduced independently by Skrekovski and Eaton and Hull. Because the rest of3-coloring problem is more and more difficult, a lot of scholars look on the improper3-coloring. They are approaching to3-coloring of some graphs step by step by solving improper3-coloring. In1976, Steinberg conjectured that every planar graph without4-cycles and5-cycles is (0,0,0)-colorable. In2007, Zhang and Xu gave a question that every plane graph without adjacent triangles is (3,1)*-choosable.This master thesis mainly discuss the improper coloring of planar graphs accord-ing the above conjectures and questions. In chapter1, we introduce some definitions and give a brief survey of improper coloring. In chapter2, we mainly discuss (1,1,0)-coloring of planar graphs with cycles constraints and improve some known results on the improper coloring of planar graphs. In chapter3, we study (3,1)*-choosability of planar graphs with cycles constraints.