Geodesic
Generalized Sum List Colorings of Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 689-703.

Voir la notice de l'article provenant de la source Library of Science

A (graph) property 𝒫 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 𝒫. If to each vertex v of a graph G a list L(v) of colors is assigned, then in an (L, 𝒫 )-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 𝒫. The 𝒫-sum choice number X_sc^𝒫 (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, 𝒫 )-coloring of G. We state some basic results on monotonicity, give upper bounds on the 𝒫-sum choice number of arbitrary graphs for several properties, and determine the 𝒫-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 
@article{DMGT_2019_39_3_a6,
     author = {Kemnitz, Arnfried and Marangio, Massimiliano and Voigt, Margit},
     title = {Generalized {Sum} {List} {Colorings} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {689--703},
     publisher = {mathdoc},
     volume = {39},
     number = {3},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a6/}
}
TY  - JOUR
AU  - Kemnitz, Arnfried
AU  - Marangio, Massimiliano
AU  - Voigt, Margit
TI  - Generalized Sum List Colorings of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 689
EP  - 703
VL  - 39
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a6/
LA  - en
ID  - DMGT_2019_39_3_a6
ER  - 
%0 Journal Article
%A Kemnitz, Arnfried
%A Marangio, Massimiliano
%A Voigt, Margit
%T Generalized Sum List Colorings of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 689-703
%V 39
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a6/
%G en
%F DMGT_2019_39_3_a6
Kemnitz, Arnfried; Marangio, Massimiliano; Voigt, Margit. Generalized Sum List Colorings of Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 689-703. http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a6/

[1] A. Berliner, U. Bostelmann, R.A. Brualdi and L. Deaett, Sum list coloring graphs, Graphs Combin. 22 (2006) 173–183. doi:10.1007/s00373-005-0645-9

[2] C. Brause, A. Kemnitz, M. Marangio, A. Pruchnewski and M. Voigt, Sum choice number of generalized θ-graphs, Discrete Math. 340 (2017) 2633–2640. doi:10.1016/j.disc.2016.11.028

[3] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5–50. doi:10.7151/dmgt.1037

[4] E. Drgas-Burchardt and A. Drzystek, General and acyclic sum-list-colouring of graphs, Appl. Anal. Discrete Math. 10 (2016) 479–500. doi:10.2298/AADM161011026D

[5] E. Drgas-Burchardt and A. Drzystek, Acyclic sum-list-colouring of grids and other classes of graphs, Opuscula Math. 37 (2017) 535–556. doi:10.7494/OpMath.2017.37.4.535

[6] J. Harant and A. Kemnitz, Lower bounds on the sum choice number of a graph, Electron. Notes Discrete Math. 53 (2016) 421–431. doi:10.1016/j.endm.2016.05.036

[7] G. Isaak, Sum list coloring 2 × n arrays, Electron. J. Combin. 9 (2002) #N8.

[8] G. Isaak, Sum list coloring block graphs, Graphs Combin. 20 (2004) 499–506. doi:10.1007/s00373-004-0564-1

[9] A. Kemnitz, M. Marangio and M. Voigt, Bounds for the sum choice number, Electron. Notes Discrete Math. 63 (2017) 49–58. doi:10.1016/j.endm.2017.10.061

[10] A. Kemnitz, M. Marangio and M. Voigt, On the -sum choice number of graphs for 1 -additive properties, Congr. Numer. 229 (2017) 117–124.

[11] M.A. Lastrina, List-Coloring and Sum-List-Coloring Problems on Graphs, Ph.D. Thesis (Iowa State University, 2012).