(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., University of Vermont, Burlington, VT 05401-1455 USA

November, 2003