T-CHOOSABILITY IN GRAPHS

Given a set of nonnegative integers T, and a function T which assigns a set of integers S(upsilon) to each vertex upsilon of a graph G, an T -list T-coloring of G is a vertex-coloring (with positive integers) of G such that c(upsilon) is an element of S(upsilon) whenever upsilon i s an element of V(G) and \c(u) - c(w)\ is not an element of T whenever (u,w) is an element of E(G). For a fixed T, the T-choice number T-ch( G) of a graph G is the smallest number k such that G has an T-list T-c oloring for every collection of sets S(upsilon) of size k each. Exact values and bounds on the T-r,T-s-choice numbers where T-r,T-s = {0, s, 2s,...,rs} are presented for even cycles, notably that T-r,T-s-ch(C-2 n) = 2r + 2 if n greater than or equal to r + 1. More bounds are obtai ned by applying algebraic and probabilistic techniques, such as that T -ch(C-2n)less than or equal to 2\T\ if 0 is an element of T, and c(1) r log n less than or equal to T-r,T-s-ch(K-n,K-n)less than or equal to c(2)r log n for some absolute positive constants c(1), c(2). (C) 1998 Elsevier Science B.V. All rights reserved.