Multiple List Colouring And On-line DP-colouring Of Graphs

A b-fold colouring of a graph G is a mapping f which assigns to each vertex v a set f(v)of b colours so that f(v)∩ f(u)=(?) for adjacent vertices u,v.We say G is(a,b)-choosable if for any a-list assignment L of G,there is a 6-fold colouring f such that f(v)(?)L(v)for each vertex v.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 DP-chromatic number of a graph G is the infimum of those real numbers r such that G is([rm],m)-DP-colourable for every positive integer m.On-line DP-colouring is the online version of DP-colouring.This thesis studies two problems:(1)multiple list colouring and multiple DP colouring of planar graphs,(2)On-line DP-chromatic version of Ohba type theorem.i.e.graph G with |V(G)| close to x(G)has On-line DP-chromatic number equals chromatic number.We prove the following results:(1)Assume G is a planar graph without 3-cycles and normally adjacent 4-cycles,X is an independent set of G and m is a positive integer.If L is a list-assignment of G such that for v ∈ V(G)-X,|L(v)|≥ 4m and for v∈ X,|L(v)|≥3m,then G is(L,m)-choosable.(2)Every planar graph without 3-cycles and normally adjacent 4-cycles is(7m,2m)DP-colourable for every positive integer m.Therefor,the fractional DP-chromatic number of such graphs is at most 7/2.(3)If G is a graph with(?),then the On-line DP-chromatic number of G is equal to its chromatic number.