Multiple Online Coloring And Generalized List Coloring

This thesis studies multiple list coloring,multiple online list coloring of Ohba Conjecture and generalized list coloring of graphsSuppose G is a hereditary family of graphs,that is if H ? G,H' is the induced subgraph of H,then H' ?G.Assume G is a graph,a h-coloring of G colors the vertices of G with k colors so that the subgraph induced by each color class is contained in G.Analogously,we can define the list coloring of G.If G is a family of forest,then the corresponding chromatic number of G is called vertex arboricity and list vertex arboricity,denoted by p?G?and ?l?G?respectively.Wang,Wu,Yan and Xue researched the relationship between p?G?and ?l?G?,as well as ?l?G?and ?l?G?.They conjectured that ?2?G?? 2?l?G?.This thesis disproves the conjecture and proved that for any integer k? 2,there is a graph G with pi?G?=k and ?l?G?=k?k+ 1?This paper introduces the online list version of fractional arboricity ?p*-?G?.We prove that for any finite graph G,?*?G?=?p*?G?.This result generalizes a classical result of Alon,Tuza,Voigt,who proved that the fractional choice number of a graph equals its fractional chromatic number.This paper studies multiple version of online Ohba Conjecture.Ohba Conjecture claims that ?l?G?=x?G?if |V?G?| ? 2??G?+ 1.This conjecture has been proved by Noel,Reed and Wu in 2015.In 2012,Huang,Wong,Zhu proposed the online version of Ohba Conjecture:???G?=x?G?if |V?G?|?2??G?.The online version of Ohba Conjecture is still widely open.We conjecture that if |V?G?| ?2??G?,then for any integer m,G is?x?G?m,m?-paintable.This thesis proved that for any graph G,if|V?G?| ?x?G?+???G?-1?^1/2,then for any integer m,G is?x?G?m,m?-paintable.