|
AlI 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.Assign each vertex υa coloring set L(υ),then L={L(υ)|υ∈V} is said to be a color list.If for any vertex υ∈V,we can choose a color Φ(υ)from the corresponding color list L(υ),such that Vυυ∈E(G),Φ(υ)≠Φ(υ),then G is L-colorable.If for any color list L,such that|L(υ)|≥k,G is L-colorable,then G is said to be k-list-colorable.or k-choosable.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)suchh that the vertex-induced subgraph G[Vi]has the maximum degree at most di,where Vi is the subset of vertices colored i,i∈{1,2,…,k),then G is said to be improperly(d1,d2,…,dk)-colorable, in short,(d1,d2…,dk)-colorable.If d1=d2=…=dk=d,then G is called d-improperly k-colorable,or(k,d)*-colorable.Let d be a non-negative integer and L a k-list-assignment of G. If,for every L={L(υ)|υ∈V,|L(υ)|≥k}and everyυ∈V,we can use a color from L(υ)to color υ such that the vertex-induced subgraph G[Vi]has the maximum degree at most d,where Vi is the subset of vertices colored i,then G is said to be(k,d)*-list colorable, or(k,d)*-choosable.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.This master thesis, consisting of four chapters, focuses on this conjecture and question, 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 coloring. In the second chapter, we mainly discuss the improper coloring of planar graphs with neither cycles of length4nor5. In the third chapter, we mainly discuss the improper coloring of planar graphs with neither cycles of length4nor6. In the forth chapter, we mainly discuss the improper list coloring of planar graphs without cycles of length4.
|