DP-coloring Of Planar Graphs

Let G be a finite and simple graph.For a graph G,we use V(G)and E(G)to denote its vertex set and edge set,respectively.A proper k-coloring of the graph G is a mapping f:V(G)?{1,2,...,k} such that f(x)?f(y)for any xy ? E(G).The minimum positive integer k such that G admits a proper k-coloring is called the chromatic number of G,denoted by x(G).We say that L is a k-list assignment for the graph G if it assigns a list L(v)of possible colors to each vertex v of G with |L(v)|?k.If G has a proper coloring f such that f(v)?L(v)for each vertex v ? V(G),then we say that G is L-colorable.The graph G is k-list colorable(or k-choosable)if it is L-colorable for every k-list assignment L.The smallest positive integer k such that G is k-choosable is called the list chromatic number of G,denoted by ?l(G).Let L be a k-list assignment of V(G).For each edge uv ? E(G),let MlL,uv be a matching between the sets {u}×L(u)and {v}×L(v).Let ?L={MLuv:uv?E(G)},which is called a matching assignment cover L.Then a graph HL is said to be the?L-cover of G if it satisfies all the following four conditions:(?)The vertex set of HL is U?u?V(G)({u}×L(u))={(u,c):u?V(G),c?L(u)};(?)For all u ? V(G),the set {u}×L(u)induces a clique in HL;(?)If uv ? E(G),then the edges between {u} ×L(u)and {v}×L(v)are those of ML,uv;(?)If uv(?)E(G),then there are no edges between {u}×L(u)and {v}×L(v).An ?L-coloring of G is an independent set I in the ?L-cover with |I|=|V(G)|.The DP-chromatic number is the minimum positive integer k such that G admits an?L-coloring for each k-list assignment L and each matching assignment ?L cover L,denoted by ?Dp(G).DP-coloring was introduced by Dvorak and Postle in 2015.They proved that?Dp(G)?5 for every planar graph G.In 1993,Voigt presented an example of a pla-nar graph which is not 4-choosable.It is also not DP-4-colorable by ?Dp(G)??l(G).Recently,the research of DP-4-coloring of planar graphs attracts much more attention around the world.In this paper,we shall investigate this problem and give several new sufficient conditions for planar graphs to be DP-4-colorable.The framework is shown as follows:In Chapter 1,we introduce some definitions and a brief survey of DP-4-coloring.In 2019,Huang and Wang et al proved that each planar graph of diameter at most two is 4-choosable.In Chapter 2,we improve this result and get the following result:(1)Each planar graph of diameter at most two is DP-4-colorable.In Chapter 3 and Chapter 4,we make use of contradiction to investigate the struc-tures of minimal counterexample graph,and then use discharging method to get a con-tradiction.More precisely,we shall prove the following results:(2)Each planar graph without chordal 6-cycles and necklaces is DP-4-colorable.(3)Each planar graph without 4-cycles adjacent simultaneously to 5-cycles and 6-cycles is DP-4-colorable.