List Colorings with Distinct List Sizes, the Case of Complete Bipartite Graphs

Füredi, Zoltán and Kántor, Ida (2016) List Colorings with Distinct List Sizes, the Case of Complete Bipartite Graphs. JOURNAL OF GRAPH THEORY, 82 (2). pp. 218-227. ISSN 0364-9024

	Text 1_s2.0_S157106530900095X_main_u.pdf Restricted to Registered users only Download (190kB) | Request a copy
Preview	Text 2385.pdf Download (160kB) | Preview

Abstract

Let f:V→N be a function on the vertex set of the graph G=(V,E). The graph G is 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, Surveys in Combinatorics, 1993 (Keele), London Mathematical Society Lecture Note Series, Vol. 187, Cambridge University Press, Cambridge, 1993, pp. 1-33, Random Struct Algor 16 (2000), 364-368) that if G has average degree d, then the usual choice number χℓ(G) is at least Ω(logd), so they grow simultaneously. In this article, 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. © 2015 Wiley Periodicals, Inc.

Actions (login required)

Edit Item