2013/05/08 by Michelle Lastrina, Michael Young, Lastrina, Michelle +1
Mathematics · #05C15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15
paper · pdf · doi:10.48550/arxiv.1305.1962
14 pages, 11 figures
arxiv created 2013/05/08 · arxiv updated 2013/05/10
Let G=(V,E) be a graph and let f be a function that assigns list sizes to the vertices of G. It is said that G is f-choosable if for every assignment of lists of colors to the vertices of G for which the list sizes agree with f, there exists a proper coloring of G from the lists. The sum choice number is the minimum of the sum of list sizes for f over all choosable functions f for G. The sum choice number of a graph is always at most the sum |V|+|E|. When the sum choice number of G is equal to this upper bound, G is said to be sc-greedy. In this paper, we determine the sum choice number of all graphs on five vertices, show that trees of cycles are sc-greedy, and present some new general results about sum list coloring.