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: |