The Study On The Improper 2-coloring Of Planar Graphs

Graph theory is a science which developed rapidly.In the recent several hundred years,it has constructed a complete theoretical system and has many applications.For example,physics,operations research,computer science,cybernetics,information theory and economic management etc.Using the graph theory,these are available to construct a mathematical model.And graph coloring is one of the chief fields in graph research.The graph coloring problem comes from the famous "Four Color Theorem",that is to say,if we want to color a map in plane such that two countries have different colors if they have one common side,we need four colors at most.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.We call this kind of coloring the proper coloring of graph G.Let d1,d2,...,dk be k non-negative integers.A graph G is(d1,d2,...,dk)-colorable,if the vertex set of G can be partitioned into subsets V1,V2,...,Vk such that the graph G[Vi]induced by Vi has maximum degree at most di for i=1,2,…,k.We call G is d-improperly k-colorable if d1=d2=...=dk=d.For a plane graph G,we use F(G)to denote its face set.We say that two cycles are adjacent if they share at least one edge.From the above definition,we know that proper coloring is a special case of im-proper coloring and improper coloring is an generalization of proper coloring.Using this concept,the famous" Four Color Theorem" can be said(0,0,0,0)-colorable[10,11].For a planar graph with(d1,d2,d3)-colorable,In 1976,Steinberg posed a conjecture that all planar graphs without 4-cycles and 5-cycles are properly 3-colorable.Although there is a disproof of this conjecture,many famous results have been obtained under the im-petus of this conjecture,such as:they proved that a planar graph without cycles of length 4 or 5 is(2,1,0)-colorable[6],(3,0,0)-colorable[9]and so on.For a planar graph with(d1,d2)-colorable,many famous results have been obtained by restricting the girth and forbidding some special circles.For example,planar graphs with girth at least 6 are(2,2)-colorable[4],Pongpat,Kittikorn[25]proved that a planar graph without cycles of length 4 or 5 is(3,5),(4,4),(2,9)-colorable with discharging method and so on.Based on the above research on 2-coloring of planar graphs,we mainly discuss the problem of improper vertex coloring of planar graphs without 4-cycles and with some special cycles forbidden.The master thesis is divided into four chapters.The first chapter introduces some basic concepts and symbols,as well as the history and current research progress of the improper coloring of planar graphs.Then we will prove the theorems by using discharg-ing in Chapter 2,Chapter 3 and Chapter 4 respectively:Theorem 1.4.1:Planar graphs with neither 4-cycles nor adjacent 5-cycles and with-out 3-cycles adjacent to k-cycle(k=5,6)are(3,7)-colorable.Theorem 1.4.2:Planar graphs without 4-cycles and 2-vertices on 3-cycles and with-out 5-cycles adjacent to k-cycle(k=5,6)are(3,7)-colorable.Theorem 1.4.3:Planar graphs without 4-cycles and 2-vertices on 3-cycles and 5-cycles without common vertices are(2,9)-colorable.