TY - JOUR

T1 - Choosability and fractional chromatic numbers

AU - Alon, N.

AU - Tuza, Zs

AU - Voigt, M.

N1 - Funding Information:
*Corresponding author. E-mail: tuza@lutra.sztaki.hu. ’ Research supported in part by the Fund for Basic Research administered by the Israel Academy of Sciences. * Research supported in part by the National Scientific Research Fund, grants 7558 and T016416.

PY - 1997/3/15

Y1 - 1997/3/15

N2 - A graph G is (a,b)-choosable if for any assignment of a list of a colors to each of its vertices there is a subset of b colors of each list so that subsets corresponding to adjacent vertices are disjoint. It is shown that for every graph G, the minimum ratio a/b where a,b range over all pairs of integers for which G is (a,b)-choosable is equal to the fractional chromatic number of G.

AB - A graph G is (a,b)-choosable if for any assignment of a list of a colors to each of its vertices there is a subset of b colors of each list so that subsets corresponding to adjacent vertices are disjoint. It is shown that for every graph G, the minimum ratio a/b where a,b range over all pairs of integers for which G is (a,b)-choosable is equal to the fractional chromatic number of G.

UR - http://www.scopus.com/inward/record.url?scp=0002443622&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0002443622&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(96)00159-8

DO - 10.1016/S0012-365X(96)00159-8

M3 - Article

AN - SCOPUS:0002443622

VL - 165-166

SP - 31

EP - 38

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

ER -