On List Colorings Of Graphs

This thesis focuses on three problems related to list colorings of graphs.The first one is on chromatic-choosability,which is motivated by a conjecture posed by Ohba and confirmed by Noel,Reed and Wu(Noel-Reed-Wu Theorem):any graph G with at most 2x(G)+1 vertices is chromatic-choosable.We study the Oh-ba 's conjecture in the settings of improper colorings,hypergraph colorings and signed graph colorings.An extension of Ohba's conjecture to improper coloring was proposed by Yan et al.:any graph with at most(d+2)?d(G)+(d+1)vertices is d-improperly chromatic-choosable,where ?d(G)is the d-improper chromatic number of G.In Chapter 2,we prove a weaker version of this conjecture,that is,any graph G with(d+3/2)?d(G)+d/2 vertices is d-improperly chromatic-choosable.In Chapter 3 we further relate d-improper colorings by words of hypergraph colorings and propose a hypergraph analogue of Ohba's conjecture:any r-uniform hypergraph G with at most r?(G)+r-1 vertices is chromatic-choosable.We show that our proposed conjecture implies the aforementioned Ohba-like conjecture for improper colorings and the one proposed by Zhen and Wu for forest colorings.To support the conjec-ture,we prove that ?l(G)=X(G)for two classes of r-uniform hypergraphs G with|V(G)|=r?(G)+r-1.We also show that the condition of the conjecture is sharp by giving two classes of r-uniform hypergraphs G with |V(G)|=r?(G)+r and Xi(G)>?(G).In Chapter 4,we give a generalization of Noel-Reed-Wu Theorem to signed graphs on zero-free colorings,which strengthens the original Noel-Reed-Wu Theorem.The second problem is on list color function and its relation with chromatic poly-nomial.We consider the properties of Pl(G,k)evaluated at k=?l(G).In Chapter 5,we show that Pl(G,?(G))>2 when |V(G)|?<2?(G).For graphs G with ex-actly 2?(G)+ 1 vertices,the same conclusion holds under the assumption of a con-jecture of Noel-Reed-Wu.We also prove that the complete bipartite graph Kn,nn-1 satisfies Pl(Kn,nn-1,n)<P(Kn,nn-1,n).In Chapter 6,using Whitney's broken cy-cle theorem we show that if k>1/ln(1+(?)(|E(G)|-1)?1.135(|E(G)|-1),then Pl(G,k)=P(G,k)and moreover the k-list assignment permitting the fewest col-orings is the constant list assignment,improving the previous results of Donner and Thomassen.We further extend this result to uniform hypergraphs by refining a broken cycle theorem given by Trinks for hypergraphs.Finally,in Chapter 7 we define Alon-Tarsi number and modulo-p Alon-Tarsi num-ber and extend the Alon-Tarsi list coloring theorem to signed graphs.Using this ex-tension we show that the Alon-Tarsi number and modulo-p Alon-Tarsi number of any signed planar graph(G,?)is at most 5,where the former result generalizes a recent re-sult of Zhu for unsigned case and the latter one implies that(G,?)is Z5-colorable.In particular,we show that any 2-colorable signed planar graph has Alon-Tarsi number at most 4 and construct a signed planar graph which is 2-colorable but not 3-choosable.