| List coloring is a generalization of graph coloring where the vertices of a graph are given lists of colors, and vertices are to be assigned colors from their lists so that adjacent vertices get different colors. Let ƒ be a function assigning list sizes to the vertices of a graph G. The function ƒ is called choosable if for every assignment of lists to the vertices of G with list sizes given by ƒ, there exists a coloring of G from the lists (with adjacent vertices receiving different colors). The sum choice number is the minimum over all choosable ƒ of the sum of the list sizes of ƒ. We first answer some questions raised in a paper of Berliner, Bostelmann, Brualdi, and Deatt. Namely, we determine the sum choice number of the Peterson graph, the Cartesian product of paths P2 □ Pn and the complete bipartite graph K 3,n. We then determine the sum choice number of P3 □ Pn. Finally, to settle a question of Isaak, Albertson, and Pelsmajer, we investigate the choosability of fan graphs, Pn✶ K1, graphs obtained by joining to a path a single vertex adjacent to each vertex of the path. The techniques developed herein have applications to other classes of graphs. |
