Sum List Coloring $2 \times n$ Arrays

Garth Isaak

Abstract


A graph is $f$-choosable if for every collection of lists with list sizes specified by $f$ there is a proper coloring using colors from the lists. The sum choice number is the minimum over all choosable functions $f$ of the sum of the sizes in $f$. We show that the sum choice number of a $2 \times n$ array (equivalent to list edge coloring $K_{2,n}$ and to list vertex coloring the cartesian product $K_2 \square K_n$) is $n^2 + \lceil 5n/3 \rceil$.


Full Text: PDF