**(a:b)-Choosability
**

A list-assignment L gives
a list of colors available at each vertex. If every list is of size k we call L about a k-list assignment. An L-coloring assigns each vertex one
of the colors in its list. Usually we want proper colorings, so that adjacent
vertices receive distinct colors. The
list-chromatic number is the smallest k such that every k-list assignment L has a proper L-coloring. Obviously, the list
chromatic number is greater than or equal to the chromatic number,
since the latter is the special case that all vertices get lists 1,...,k.

Generalizing the above, a graph is (a:b)-choosable
if for any assignment of lists of size
a, a subset of b
colors can be chosen from each vertex list such that adjacent vertices
receive disjoint sets of colors.Hence being (k:1)-choosable is equivalent to
having list-chromatic number k.
Define the b-inflation of a
graph G, G_(b), as the
composition G(K_b). So in the
b-inflation, each vertex is
replaced by a complete graph of order b,
and each edge by a regular complete bipartite graph on 2b vertices. Observe that if G is (a:b)-choosable, then G_(b) is a-choosable. The following
conjectures are from [KW].

**Conjecture:** The Weak (a:b)-Choosability Conjecture: For all a,b,t, if G is (a:b)-choosable, then G is (ta:tb)-choosable.

**Conjecture:** The Strong (a:b)-Choosability
Conjecture: For all a,b,t, if G is (a:b)-choosable, then G_(t) is (ta:b)-choosable.

**Conjecture:** The (a:b)-Choosability Equivalence
Conjecture: For all a,b, G
is (a:b)-choosable if and
only if G_(b) is a-choosable.

A very good survey on list colorings is given by Woodall [W].

**References:
**

[ERT] P. Erdos, A.L. Rubin, and H. Taylor, Choosability in graphs,** **Proc. West Coast
Conference on Combinatorics, Graph Theory and Computing, Arcata, 1979,
Congr. Numer. ** 26 **(1980) 125-157

[KW] A.V. Kostochka and D.R. Woodall, Choosability conjectures and
multicircuits, Discrete Math.,
to appear

[W] D.R. Woodall, List colourings of graphs, 269-301

** **

Submitted by: Dan Archdeacon, Dept. of Math.
and Stat.,