2011/11/01 by Zoltán Füredi, Füredi, Zoltán, Ida Kantor +1
Mathematics · #05C15 (Primary) 05C35 #05C65 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C35 #msc:05C65
paper · pdf · doi:10.48550/arxiv.1111.0234
10 pages
arxiv created 2011/11/01 · arxiv updated 2011/11/02
Let f:V → ℕ be a function on the vertex set of the graph G=(V,E). The graph G is \em f-choosable if for every collection of lists with list sizes specified by f there is a proper coloring using colors from the lists. The sum choice number, χsc(G), is the minimum of ∑ f(v), over all functions f such that G is f-choosable. It is known (Alon 1993, 2000) that if G has average degree d, then the usual choice number χ_ℓ(G) is at least Ω(log d), so they grow simultaneously. In this paper we show that χsc(G)/|V(G)| can be bounded while the minimum degree δmin(G)→ ∞. Our main tool is to give tight estimates for the sum choice number of the unbalanced complete bipartite graph Ka,q.