DP-4-colorability Of A Class Of Planar Graphs

Graph theory is one of most interesting braches of Combinatorics.It has many applications in theoretical chemistry,theoretical computer sciences and network theory etc.All graphs considered in this paper are finite,simple and planar.Mathematicians introduced the concept of “List-Coloring” in the 1970 s.Borodin conjectured that each planar graph without cycles of length 4-8 is 3-choosable in 1996.Until 2018,Dvo?ák and Postle gave an affirmative answer to it by putting forward the concept of “DP-coloring”.They transformed the problem of list-coloring of to the existence of independent set of size |(1()| in a correspondence graph.Now,we can explore more about list-coloring and try to generalize some results of list-coloring to DP-coloring.We've already know that any planar graphs are 4-colorable.In 1994,Thomassen showed that they are list-5-colorable(or 5-choosable).Dvo?ák and Postle showed that they are also DP-5-colorable.So it is natural to study DP-4-colorability of some planar graphs.We mainly obtained a new class of planar graphs which are DP-4-colorable.After the study background and literature review in Introduction,we give the details of the proof in the second chapter.The main tool to deny the existence of minimal counterexample is the discharging method.Then by Kim and Ozeki's result,we can prove that: planar graphs without 5-cycles adjacent to 6-cycles are DP-4-colorable.And as a corollary,they are also 4-choosable.Meanwhile,we can obtain a new class of sign planar graphs which are signed 4-choosable by Kim and Ozeki's another result.At the end of our thesis,we give an interesting problem for further research.