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.