Study On DP-coloring And List Coloring Problems Of Planar Graphs

In this Ph.D.dissertation,we study two kinds of vertex coloring problems of graphs: list coloring and DP coloring.A proper coloring of a graph G is a assignment of color sets to each vertex in G,such that any two adjacent vertices in G are dyed with different colors.A list assignment L of G is a mapping that assigns to each vertex v in G a list of available colors L(v).For a given list assignment L,G is L-colorable if there is a proper coloring f of G such that f(v)?L(v)for every v in G.A graph G is k-choosable if G has a L-coloring for each L with L(v)?k.List coloring was introduced by Vizing and independently by Erd(?)s,Rubin and Talor.Borodin proved that planar graphs without cycles of lengths 4 to 9 are 3-choosable,and conjectured that planar graphs without cycles of lengths 4 to 8 are 3-choosable.For list coloring of a graph G,since different vertices may have different lists,some techniques which are often used for proper coloring are not suitable for list coloring,such as the identification of vertices.To overcome this difficulty,Dvo(?)ák and Postle introduced correspondence coloring(simply write DP coloring)in 2018.By constructing the correspondence graph of G,They transformed the problem of list-coloring of G to the existence of independent set with certain properties in its correspondence graph.Dvo(?)ák and Postle proved that planar graphs without cycles of lengths 4 to 8 are3-choosable,confirmed the conjecture of Borodin.Liu and Li proved that planar graphs without adjacent cycles of length at most 8 are 3-choosable.Yin and Yu proved that(1)planar graphs without {4,5}-cycles and the distance of triangles at least 3 are DP-3-colorable;(2)planar graphs without {4,5,6}-cycles and the distance of triangles at least 2 are DP-3-colorable.In 1965,Ringel proposed the definition of 1-planar graph and gave the conjecture that every 1-planar graph is 6-colorable.Borodin proved that 6 is optimal.In this thesis,we study two kinds of vertex coloring problems of graphs: list coloring and DP coloring.This thesis consists of five chapters,as follows:In chapter 1,we give some definitions and notations used in this thesis.Then we introduce some relative conjectures and current research status of list coloring and DP coloring.At last,we show the main results of this thesis.In chapter 2,we study the list coloring of planar graphs by DP coloring and prove the following results:(1)Planar graphs without {4,6,8}-cycles are 3-choosable,which improves that planar graphs without {4,6,8}-cycles are 3-colorable in the result of Wang and Chen(2007),and also improves the result of Dvo(?)ák and Postle(2018);(2)planar graphs without {4,6,9}-cycles are 3-choosable,which improves that planar graphs without {4,6,9}-cycles are 3-colorable in the result of Kang,Jin and Wang(2016).In chapter 3,we study the DP coloring of planar graphs and prove the following results:(1)Planar graphs with the distance of {3,4,5}-cycles at least 3 from each other are DP-3-colorable,which improves the result of Yin and Yu(2019);(2)planar graphs with the distance of {3,4,5,6}-cycles at least 2 from each other are DP-3-colorable,which improves the result of Yin and Yu(2019);(3)planar graphs without{4,5,8,10}-cycles are DP-3-colorable,which improves that planar graphs without{4,5,8,10}-cycles are 3-choosable in the result of Wang and Wu(2011).In chapter 4,we study the DP coloring of 1-planar graphs and prove the following result that 1-planar graphs without {3,4}-cycles are DP-5-colorable.In chapter 5,we give a summary of this thesis,and put forward some further research problems and potential research directions.