DP-coloring Of Planar Graphs And Graph Knitted Problems

Graph coloring problems are very popular in graph theory.It originates from the famous "four color problem".It is widely applied to information theory,computer science and artificial intelligence,and so on.In this thesis,We study DP-coloring of planar graphs and knitted graphs,which are mainly related to four color problem.This thesis consists of eight sections,as follows:In section one,we give some definitions and notations that we needed in this paper.After that,we introduce the research problems and background respectively.In section two,we study a conjecture related to list coloring introduced by Borodin in 1996.That is:All planar graphs without 4 to 8 cycles are 3-choosable.Dvorak and Postle confirmed this longstanding conjecture by using DP-coloring in 2017.We improve this result by showing that all planar graphs with adjacent cycles of length at most 8 are 3-choosable.In section three,based on the methods metioned in section two,we try to solve some popular topics in three-color field of planar graphs with the help of DP-coloring.We study the DP-3-coloring of planar graphs.We improve some results from list-3-coloring to DP-3-coloring.We construct a subgraph called“near-(k-1)-degenerate”to deal with the trouble in this improvement.In section four,based on the results given in section three,we further study planar graphs without {4,a,b,9}-cycles,where 5 ?a? b? 8.We proved that all planar graphs without 4,9-cycles and two cycles of length from {5,6,7} are DP-3-colorable.In section five,we extend the research focus from three-color problem to four-color problem.We focus on the conjecture posed by Wang and Lih.[54]in 2002:Planar graphs without adjacent triangles are 4-choosable.We prove that planar graphs without 4 cycles adjacent to two triangles are DP-4-colorable.This result is a step forward towards this conjecture,also improve the result of Kim.and Yu[31].In section six,in order to find sufficient conditions for planar graphs to be DP-4-colorable,we prove that planar graphs without 7-cycles and butterflies;are DP-4-colorable.The new method introduced by this result can also solve more problems related to this field.Without much effort,we can greatly simplify the result:Planar graphs without 7-cycles are 4-choosable.In section seven,note that we have studied the cases when the chromatic num-ber is small.In general case,we study some problems about the most famous conjecture,Hadwiger's conjecure,in graph coloring field.Specially,we study the connectivity property of the minimum counterexample of this conjecture.We give the minimum degree condition for a graph to be knitted,which plays an important role in the study of k-contraction-critical graph.In section eight,we summarize the research issues involved in this thesis,and put forward some suggestions for the research direction in the future.