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

Abstract:
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.
Keywords:
sum list coloring, sum choice number, generalized sum list coloring, additive hereditary graph property

Links:
PDF