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.