On The Correspondence Coloring And Relaxation Coloring Of Planar Graphs

Four-color conjecture,also known as the four-color problem,is one of the world’s three major mathematical conjectures.The four-color problem states that"every map can be colored in four colors such that neighboring countries colored differ-ently." In other words,a map only needs four colors to be marked without causing confusion.In a concise mathematical language,it means that "the plane is arbi-trarily subdivided into non-overlapping areas,and each area can always be marked with one of the four Numbers of 1234 so that adjacent areas get different numbers.When we talk about adjacent areas,we’re talking about a whole section of boundary that s common.Two regions are not adjacent if they meet only at one or a finite number of points.Because coloring them in the same color doesn’t cause confusion.Although many people have proved that it is impossible to construct five or more pairwise connected regions in a two-dimensional plane,they have not raised it to the level of logical relations and two-dimensional inherent properties,resulting in many pseudo-counter examples.However,these are exactly the textual research and development promotion of the rigor of graph theory.In June 1976,two different electronic computers at the university of Illinois in the United States,spent 1200 hours,made 10 billion judgments,the result is that not even one map need five colors,finally proved the four-color theorem via computation method.However,this method relies on a large number of calculations,which does not conform to the rigorous mathematical logic system.Therefore,there are still numerous experts and scholars who devote themselves to the research and want to seek the rigorous mathematical proof of the four-color theorem.Therefore,graph coloring has always been a central and hot issue in graph theory.Graph coloring theory has many branches,such as edge coloring,vertex coloring,surface coloring and total coloring.Among them,the most studied and the most complete result is the vertex coloring of the graph.In this paper,two kinds of vertex coloring areas of graphs are studied:DP-coloring and relaxation coloring.This paper is mainly composed of four chapters,the main content is as follows:In the first chapter,we first give the basic concept and mark used in this paper,and introduces the background and research status of strong edge coloring of graph.Finally,we gives the main results.In the second chapter,we focus on correspondence coloring(DP-coloring).We proved two results:· One is that,a planar graph G is DP-3-colorable,if G contains no 4 or 5-cycles,while the distance between triangles is no less than 3,or if G contains no cycles of length from 4 to 6,while the distance between triangles is no less than 2.It’s an improvement of the results of Montassier,Raspaud and Wang[33].Our result is strong because there exists such a graph G that satisfies containing no cycles with a length of 4 or 5 as well as the distance between the triangles is no less than 1 which still cannot be 3-choosable.· The other is that,if G contains no cycles of length from {5,6,7},while the dis-tance between triangles is at least 2,then G is DP-3-colorable.This improves the result of Li,Chen and Wang[29]in 2016.In the third chapter,we proved that,each planar graph without 5-cycles,or K4-,or adjacent 4-cycles is(2,0,0)-colorable and improved the results of Chen,Wang,Liu and Xu[16],and the result of Liu,Li and Yu[30].Since Steinberg conjecture is disproved in 2016,our result is meaningful.In the forth chapter,the end of this paper,we puts forward some research questions that can be further considered.