“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 522
School of Mathematics
  Title:   Relations among the fractional chromatic, choice, Hall, and Hall-condition numbers of simple graphs
  Author(s): 
1.  P. D. Johnson Jr.
2.  A. J. W. Hilton
3.  A. Daneshgar
  Status:   Published
  Journal: Discrete Math.
  No.:  1-3
  Vol.:  241
  Year:  2001
  Pages:   189-199
  Supported by:  IPM
  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);HG], 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
scroll left or right