In online list coloring [introduced by Zhu (Electron J Comb 16(1):#R127, 2009) and Schauz (Electron J Comb 16:#R77, 2009)], on each round the set of vertices having a particular color in their lists is revealed, and the coloring algorithm chooses an independent subset of this set to receive that color. For a graph $$G$$G and a function $$f:\,V(G)\rightarrow {\mathbb N}$$f:V(G)?N, the graph is $$f$$f-paintable if there is an algorithm to produce a proper coloring when each vertex $$v$$v is allowed to be presented at most $$f(v)$$f(v) times. The sum-paintability of $$G$$G, denoted $$\chi _{sp}(G)$$?sp(G), is $$\min \{\sum f(v):\,G$$min{?f(v):G is $$f$$f-paintable$$\}$$}. Basic results include $$\chi _{sp}(G)\le |V(G)|+|E(G)|$$?sp(G)≤|V(G)|+|E(G)| for every graph $$G$$G and $$\chi _{sp}(G)=(\sum _{i=1}^{k} \chi _{sp}(H_i))-(k-1)$$?sp(G)=(?i=1k?sp(Hi))-(k-1) when $$H_{1},\ldots ,H_{k}$$H1,?,Hk are the blocks of $$G$$G. Also, adding an ear of length $$\ell $$l to $$G$$G adds $$2\ell -1$$2l-1 to the sum-paintability, when $$\ell \ge 3$$l?3. Strengthening a result of Berliner et al., we prove $$\chi _{sp}(K_{2,r})=2r + \min \{l+m:\,lm>r\}$$?sp(K2,r)=2r+min{l+m:lm>r} . The generalized theta-graph$$\Theta _{\ell _{1},\ldots ,\ell _{k}}$$?l1,?,lk consists of two vertices joined by internally disjoint paths of lengths $$\ell _{1},\ldots ,\ell _{k}$$l1,?,lk. A book is a graph of the form $$\Theta _{1,2,\dots ,2}$$?1,2,?,2, denoted $$B_r$$Br when there are $$r$$r internally disjoint paths of length 2. We prove $$\chi _{sp}(B_r)=2r + \min _{l,m\in \mathbb {N}}\{l+m:\,m(l-m)+{m\atopwithdelims ()2}>r\}$$?sp(Br)=2r+minl,m?N{l+m:m(l-m)+m2>r}. We use these results to determine the sum-paintability for all generalized theta-graphs.
['James M. Carraher', 'Thomas Mahoney', 'Gregory J. Puleo', 'Douglas B. West']
Sum-Paintability of Generalized Theta-Graphs