Some Sufficient Conditions For A Graph To Be DP-4-Colorable

Since 1736,after the Swiss mathematician Euler proposed the Seven Bridges of K?nigsberg,graph theory taking graph as research object has been widely recognized.The graph coloring problem is an important branch of graph theory.The “Four-Color Conjecture”appeared in 1852 is the origin of the graph coloring problem.In order to consider some problems on the proper vertex coloring problem of graphs,in 2015,Dvo?ák and Postle considered a generalization of a list coloring.They call it a correspondence coloring,but we call it a DPcoloring for short.Since every planar graph is DP-5-colorable,rather than DP-4-colorable,so it is necessary to consider the sufficient conditions for planar graph or toroidal graph to be DP-4-colorable.Considering on the graph is DP-4-colorable,we can consider the related papers that the graph is 4-choosable,and then further consider the graph is a sufficient condition for4-choosable whether or not it can be used on a sufficient condition that the graph is DP-4-colorable.For example,every planar graph without 4-cycles adjacent to triangles is 4-choosable,and can also be obtained by considering,every planar graph without 4-cycles adjacent to triangles is DP-4-colorable.Thus,finding sufficient conditions for planar graphs to be DP-4-colorable is an interesting problem.In this thesis,it is mainly divided into four chapters.The first chapter is mainly about some definitions and notations,as well as some consider status domestic and international.The second chapter mainly considers the problem that the planar graph and the toroidal graph are DP-4-colorable,which is directly proved by the discharging method in the consider process.The third chapter mainly considers the planar graph with some restricted cycles which is DP-4-colorable.The fourth chapter is the summary and prospects.