A. Kemnitz, M. Marangio, M. Voigt
Generalized sum list colorings of graphs
Discussiones Mathematicae Graph Theory
Received 16.10.2017, Revised 05.08.2018, Accepted 06.09.2018, doi: 10.7151/dmgt.2174

A (graph) property \pr{P} is a class of simple finite graphs closed under isomorphisms. In this paper we consider generalizations of sum list colorings of graphs with respect to properties \pr{P}. If to each vertex v of a graph G a list L(v) of colors is assigned, then in an (L,\pr{P})-coloring of G every vertex obtains a color from its list and the subgraphs of G induced by vertices of the same color are always in \pr{P}. The \pr{P}-sum choice number χsc\pr{P}(G) of G is the minimum of the sum of all list sizes such that, for any assignment L of lists of colors with the given sizes, there is always an (L,\pr{P})-coloring of G. We state some basic results on monotonicity, give upper bounds on the \pr{P}-sum choice number of arbitrary graphs for several properties, and determine the \pr{P}-sum choice number of specific classes of graphs, namely, of all complete graphs, stars, paths, cycles, and all graphs of order at most 4.
sum list coloring, sum choice number, generalized sum list coloring, additive hereditary graph property