Relations among the fractional chromatic, choice, Hall, and Hall-condition numbers of simple graphs

Hall's condition for the existence of a proper vertex list-multicoloring of a simple graph G has recently been used to define the fractional Hall and Hall-condition numbers of G, hf (G) and s(f)(G). Little is known about h(f)(G), but it is known that s(f)(G) = max[\V(H)\ alpha (H); H less than or equal to G], where 'less than or equal to' means 'is a subgraph of' and alpha (H) denotes the vertex independence number of H. Let chi (f) (G) and c(f)(G) denote the fractional chromatic and choice (list-chromatic) numbers of G. (Actually, Slivnik has shown that these are equal, but we will continue to distinguish notationally between them.) We give various relations among chi (f)(G), c(f)(G), h(f)(G), and s(f)(G), mostly notably that chi (f)(G) = c(f)(G) = s(f)(G), when G is a line graph. We give examples to show that this equality does not necessarily hold when G is not a line graph. Relations among and behavior of the 'k-fold' parameters that appear in the definitions of the fractional parameters are also investigated. The k-fold Hall numbers of the claw are determined and from this certain conclusions follow-for instance, that the sequence (h((k))(G)) of k-fold Hall numbers of a graph G is not necessarily subadditive. (C) 2001 Elsevier Science B.V. All rights reserved.