REAL

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

[img] Text
1_s2.0_S157106530900095X_main_u.pdf
Restricted to Registered users only

Download (185Kb) | Request a copy
[img]
Preview
Text
2385.pdf

Download (157Kb) | 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.

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 > QA166-QA166.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)

View Item View Item