Multiple List Coloring Of Graphs And On-line DP-coloring Of Graphs

This thesis studies three graph coloring problems:Strong fractional choice num-ber of series-parallel graphs,DP-coloring of graphs with two crossings,On-line DP-coloring of locally planar graphs.The strong fractional choice number of a graph G is the infimum of those real numbers r such that G is([rm],m)-choosable for every positive integer m.The strong fractional choice number of a family(?)of graphs is the supremum of the strong fractional choice number of graphs in(?).The strong fractional choice number of planar graphs were studied in[36]and[17].Let P denote the family of planar graphs and for a positive integer k,let Pk be the family of planar graphs containing no cycles of length k.It was proved in[36]that 5? ch*f(P)?4+2/9 and prove in[17]that 4?ch*f(P3)?3+1/17.The exact value of the strong fractional choice numbers of P and P3 remain open.In this thesis,we study the strong fractional choice number of a special class of planar graph:series-parallel graphs.In Chapter 2,we proved that for every integer k,let Qk={G:G is a series-parallel graph with girth at least k},then ch*f(Qk)=2+1/[k+1/4].In order to prove planar graphs without cycles of length 4-8 are 3-choosable,Z.Dvorak and L.Postle[9]introduced DP-coloring(called Corresponding coloring in this paper).In 2018,A.Bernshte,yn and A.Kostochka[3]gave an alternate definition of DP-coloring.There are some differences between DP-coloring and list coloring:In list coloring,identical color cannot be assigned to two adjacent vertices.In DP-coloring,one assign a matching between colors in the lists of two adjacent vertices,and matched pair of colors cannot be assigned to these two vertices.DP-coloring is a generalized list coloring,so results of the DP-coloring is stronger than the list coloring.Thomassen[28]proved every planar graphs are 5-choosable.This result was strengthened by Dvorak,Lidicky and Skrekovski,who proved in[8]that every graphs with two crossings are 5-choosable.In Chapter 3,we proved that graphs with two crossings are 5-DP-colorable,which is a further generalization of the above results.In 2020,S.Kim,A.Kostochka,X.Li and X.Zhu[20]introduced On-line DP-coloring by combining the definition of DP-coloring with the definition of On-line list coloring.This concept is not only a generalization of On-line list coloring,but also of DP-coloring.Thomassen[29]proved that graphs in a surface S with sufficiently large edge-width are 5-colorable.This result was strengthened by DeVos,Kawarabayashi and Mohar,who proved in[6]that every graph embedded in a fixed surface with sufficiently large edge-width is 5-choosable.This result was further strengthened by Han and Zhu,who proved in[15]that every graph embedded in a fixed surface with sufficient ly large edge-width is 5-paint able.In Chapter 4,we prove that every graph embedded in a fixed surface with sufficiently large edge-width is 5-DP-paintable,which is a further generalization of the above results.