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 φ(φ)≠φ(y) whenever xy ∈ E. Equivalently, a k-coloring of G is a partition of the vertex set V into k subsets Vi, V2,..., Vk such that G[Vi] is edgeless, i∈1,2,..., k}. G is called k-colorable if it has a k-coloring.Let d1, d,2,..., 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[V1] has maximum degree at most di, where Vi={v∈ V|φ(v= i}. A graph G is called{d1,d-2,...,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.Note that 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 (d1’,d2’,...,dk’)-colorable, when-ever di’≥ di 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. Since it is greatly difficult to approach this conjecture, Erdos advise people to consider a relaxation of this problem:whether there is a constant C, such that planar graphs without cycles of length from 4 to C are 3-colorable or not. Surrounding the conjecture and its related question, 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. In the second chapter, there is the proof of improper coloring of planar graphs. In the third chapter, there is the proof of proper coloring of planar graphs.