Improper Coloring Of Plane Graphs

All graphs considered here are finite,simple and undirected.Let G =(V,E)be a graph,k be a positive integer.A k-coloring of G is a mapping ?:V ? {1,2,...,k}such that ?(x)? ?(y)whenever xy E E.G is called k-colorable if it has a k-coloring.Let d1,d2,...,dk be k non-negative integers,and G =(V,E)be a graph with the sets of vertices and edges V and E,respectively.A(d1,d2,...,dk)-coloring of G is a mapping ?:V?{1,2,...,k} such that the subgraph G[Vi]has maximum degree at most di,where Vi= {v?V|?(v)= i}.A graph G is called(d1,d2,...,dk)-colorable if it admits a(d1,d2,...,dk)-coloring.If d1=d2=...dk= d,then G is called d-improperly k-colorable,or(k,d)*-colorable.Clearly a graph G is properly vertex k-colorable if and only if it is(0,0,...,0)-colorable;and if G is(d1,d2,...,dk)-colorable then it is(d'1,d2',...,d'k)-colorable,when-ever di?d'i for all i = 1,2,...,k.In 1976,Steinberg put forward a famous conjecture:All planar graphs with cycles of length neither 4 nor 5 are 3-colorable.Surrounding the Steinberg conjecture,people put forward a famous Bordeaux conjecture:Every planar graph with neither 5-cycles nor intersecting triangles is(3,0)*-colorable(the weak version)and every planar graph with neither 5-cycles nor adjacent triangles is(3,0)*-colorable(the strong version)and Nsk's conjecture:Every planar graph without 3-cycles adjacent to cycles of length 3 or 5 is(3,0)*-colorable.Surrounding the above famous conjectures,people exerted themselves to make related research and got a series of achievements.This paper consists of three chapters,focusing on the conjecture and question above,which has improved several previous results.In the first chapter,there are some defini-tions and a brief survey of proper coloring and improper coloring.In the second chapter,it is shown that every planar graph without 4-cycles adjacent to 3-cycles or 4-cycles and without 7-cycles is(1,1,0)-colorable and Planar graphs without adjacent cycles of length at most five are(1,1,0)-colorable.In the third chapter,Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are(3,1)*-colorable...