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. Equivalently, a k-coloring of G is a par-tition of the vertex set V into k subsets, V1,V2, …, Vk such that G[Vi] is edgeless, i ∈{1,2,..., k}. G is called k-colorable if it has 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[Vi] has maximum degree at most di, where 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 ^-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 (d’1, d’2,..., d’k)-colorable, whenever d’i> 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 definitions and a brief survey of proper coloring and improper coloring. In the second chapter, there are three of the research results:planar graphs without cycles of length 4 or i (i E{5,7,8}) are (2,0,0)-colorable. In the third chapter, there is the proof of planar graphs with cycles of length neither 4 nor 6 are (1,0,0)-colorable.