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. 218227. ISSN 03649024
Text
1_s2.0_S157106530900095X_main_u.pdf Restricted to Registered users only Download (190kB)  Request a copy 


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 fchoosable 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 fchoosable. It is known (Alon, Surveys in Combinatorics, 1993 (Keele), London Mathematical Society Lecture Note Series, Vol. 187, Cambridge University Press, Cambridge, 1993, pp. 133, Random Struct Algor 16 (2000), 364368) 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.
Item Type:  Article 

Uncontrolled Keywords:  list chromatic number; GRAPHS 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA166QA166.245 Graphs theory / gráfelmélet 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  03 Jan 2017 15:14 
Last Modified:  03 Jan 2017 15:14 
URI:  http://real.mtak.hu/id/eprint/44189 
Actions (login required)
Edit Item 