Premium
List Colorings with Distinct List Sizes, the Case of Complete Bipartite Graphs
Author(s) -
Füredi Zoltán,
Kantor Ida
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21896
Subject(s) - combinatorics , mathematics , bipartite graph , list coloring , vertex (graph theory) , bounded function , graph , discrete mathematics , degree (music) , graph power , line graph , mathematical analysis , physics , acoustics
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,χ s c( 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 Ω ( log d ) , so they grow simultaneously. In this article, we show thatχ s c( 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 K a , q .