Improper Coloring Of Planar Graphs Without4-cycles

The improper coloring is an extension of proper coloring. Let G=(V,E) be a graph, k be a positive integer, d1, d2,…,dk be k nonnegative integers, a graph G=(V, E) is improperly (d1,d2,… dk)-colorable, if one can use k colors, say,1,…, k, to color the vertices of G such that every vertex colored i has at most di neighbors colored i for i=1,…, k. Any such coloring is called a (dls d2,…, dk)-coloring of G. If d1=d2=…=dk=d, then the graph G is called (k, d)*-colorable. If d1=d2=…=dk=0, then the graph G is called k-colorable or (k,0)*-colorable. In this thesis, we mainly investigate the improper coloring of planar graphs without4-cycles and the thesis contains four chapters.In chapter1, we introduce some definitions and notations used throughout this thesis and give a chief survey on improper coloring.In chapter2, we mainly investigate the improper coloring of planar graphs without cycles of length4,5or9. In1976, Steinberg posed a conjecture:All planar graphs without4-cycles and5-cycles are properly3-colorable. Around Steinberg conjecture, people made related research and gained a series of achievements. Up to now, the3-coloring problems of planar graphs without cycles of length4, i or j (5≤i≤j≤9) have not all been solved for the cases when i=5, j=6; i=5, j=9; i=7,j=8or i=8, j=9. In this chapter, we proved that planar graphs without cycles of length4,5or9is (1,0,0)-colorable by using the Discharging method, made a preparation for solving the3-coloring problems.In chapter3, we discuss the improper coloring of planar graphs with cycles of length neither4nor8. Considering the3-coloring problems of planar graphs with cycles of length neither4nor i (5≤i%9), Lih and W. Wang et al. proved that every planar graph with cycles of length4nor i for i G{5,6,7}) is (1,1,1)-colorable. Dong and Xu extended i to9. In this chapter, we made a further research for the case when i=8and proved that planar graphs with cycles of length neither4nor8is (3,0,0)-colorable.In the last chapter, we investigate the improper coloring of planar graphs with cycles of length neither4nor5. In order to solve the Steinberg conjecture, Chang et al. proved that every planar graph with cycles of length neither4nor5is (4,0,0)-and (2,1,0)-colorable. Very recently, Y. Wang and L. Xu showed that every planar graph with cycles of length neither4nor5is (3,0,0)-colorable and (1,1,0)-colorable. This chapter made a research about (2,0,0)-coloring, and proved that planar graphs without cycles of length4,5or intersecting triangles are (2,0,0)-colorable.