Skip to main navigation Skip to Content
Paper IPM / M / 522  


Abstract:  
Hall's condition for the existence of a proper vertex
listmulticoloring of a simple graph G has recently been used to
define the fractional Hall and Hallcondition numbers of G,
h_{f}(G) and s_{f}(G). Little is known about h_{f}(G), but it is
known that s_{f}(G)=max[V(H)/α(H);H ≤ G], where " ≤ " means "is a subgraph of" and α(H) denotes the vertex
independence number of H.
Let x_{f}(G) and c_{f}(G) denote
the fractional chromatic and choice (listchromatic) 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), c_{f}(G), h_{f}(G), and s_{f}(G),
mostly notably that χ_{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.
Download TeX format 

back to top 
COPYRIGHT 2012 © ALL RIGHTS RESERVED
Please submit your comments or questions here, or contact Webmaster  ipmic@ipm.ir