Improper Coloring Of Plane Graphs

All graphs considered in this paper 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) for any xy∈E. G is called k-colorable if it admits a k-coloring.Let di, i∈{1,2,...,k}be k non-negative integers. If we can use k colors, say1,2,...,k, to color the vertices of a graph G=(V, E) such that the vertex colored i has at most di neighbors colored i for every i∈{1,2,.... k}, then G is said to be improperly (di,d2,..., dk)-colorable, in short,(di,d2,..., dk)-colorable. If d1=d2==dk=d, then G is called d-improperly k-colorable, or (k, d)*-colorable.So proper coloring is a special case of improper coloring and improper coloring is an extension of proper coloring.In1976, Steinberg posed a conjecture:All planar graphs without4-cycles and5-cycles are properly3-colorable. Because of the great difficulty of solving the famous Steinberg conjecture, Erdos proposed to find a constant C, such that a planar grpah without cycles of length from4to C is properly3-colorable. Around the question and conjecture, people made related research and gained a series of achievements.This master thesis, consisting of six chapters, focuses on this conjecture and ques-tion, we make some improvement on several previous results. In the first chapter, we introduce some definitions and give a brief survey of proper coloring and improper col-oring. In the second chapter, we introduce that planar graphs without cycles of length4,8and i for every i∈{7,9} are (1,0,0)-colorable. In the third chapter, we intro-duce that planar graphs without cycles of length4and6are (2,0,0)-colorable. In the forth chapter, we introduce that planar graphs without cycles of length4and i for every i∈{7,8} are (1,1,0)-colorable. In the fifth chapter, we introduce that planar graphs without cycles of length4and7are (3,0,0)-colorable. In the sixth chapter, we introduce that planar graphs without cycles of length5are (1,1,1)-colorable.