(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.,
Send comments to dan.archdeacon@uvm.edu
November, 2003