Improper Coloring Of Planar Graphs

A graph G is(d1,d2)-colorable if its vertices can be partitioned into subsets V1 and V2 such that in G[Vi]every vertex has degree at most di for each i?{1,2}.It is known that every planar graph with girth 5 is(di,d2)-colorable,where(di,d2)?{(2,6),(3,5),(4,4)}.We still do not know even if there is a finite positive d such that every graph in with girth 5 is(1,d)-colorable.In 2015,Choi and Raspaud posed a problem which states that is every graph with girth 5(1,7)-colorable?A list assignment of a graph G is a function L that assigns a list L(v)of colors to each vertex v ?(G).An(L,d)*-coloring is a mapping ? that assigns a color?(v)? L(v)to each vertex v ?(VG)so that at most d neighbors of v receive color?(v).A graph G is said to be(k,d)*-choosable if it admits an(L,d)*-coloring for every list assignment L with |L(v)|>k for all v ?V(G),In 2007,Xu and Zhang conjectured every planar graph without adjacent triangles is(3,1)*-choosable.In this master thesis,we study above two coloring problems.The thesis consists of three chapters.In Chapter 1,we first collect some basic notations.Then we present a chief survey in this direction and later state the main results that we obtain.In Chapter 2,we study(1,7)-colorability of planar graphs.We prove that graphs with girth 5 without adjacent 5-cycles are(1,7)-colorable.In Chapter 3,we study(3,1)*-colorability of planar graphs.We prove that planar graphs with neither adjacent triangles nor 8-cycles are(3,1)*-choosable.