“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 522 |
|
||||||
| Abstract: | |||||||
|
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 sf(G). Little is known about hf(G), but it is
known that sf(G)=max[|V(H)|/α(H);H ≤ G], where " ≤ " means "is a subgraph of" and α(H) denotes the vertex
independence number of H.
Let xf(G) and cf(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 χf(G), cf(G), hf(G), and sf(G),
mostly notably that χf(G)=cf(G)=sf(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.
Download TeX format |
|||||||
| back to top | |||||||
