Sum List Coloring 2 by n Arrays
by
Garth Isaak
Lehigh University

For list sizes given by a function f a graph is f-choosable if for every collection of lists with sizes given by f there is a good coloring using colors from the lists. The sum list coloring number is the minimum value of the sum of the list sizes for an f-choosable f. (The regular choice number is the minimum constant function f that is f-choosable.) We show that the sum list coloring number of the 2 by n array (corresponding to the edges of a complete bipartite graph with one part of size 2) is the least integer greater than or equal to n^2 + 5n/3.

Date received: April 16, 2001