Let G = (V,E) be a simple graph and for every edge e ∈ E let L(e) be a set (list) of available colors. The graph G is called L-edge colorable if there is a proper edge coloring c of G with c(e) ∈ L(e) for all e ∈ E. A function f : E → ℕ is called an edge choice function of G and G is said to be f-edge choosable if G is L-edge colorable for every list assignment L with |L(e)| = f(e) for all e ∈ E. Set size(f) = ∑e∈E f(e) and define the sum choice index χ′sc(G) as the minimum of size(f) over all edge choice functions f of G. There exists a greedy coloring of the edges of G which leads to the upper bound χ′sc(G) ≤ 1/2 ∑v∈V d(v)2. A graph is called sec-greedy if its sum choice index equals this upper bound. We present some general results on the sum choice index of graphs including a lower bound and we determine this index for several classes of graphs. Moreover, we present classes of sec-greedy graphs as well as all such graphs of order at most 5.
@article{bwmeta1.element.doi-10_7151_dmgt_1884,
author = {Arnfried Kemnitz and Massimiliano Marangio and Margit Voigt},
title = {Sum List Edge Colorings of Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {709-722},
zbl = {1339.05138},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1884}
}
Arnfried Kemnitz; Massimiliano Marangio; Margit Voigt. Sum List Edge Colorings of Graphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 709-722. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1884/
[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[Crossref] | Zbl 1098.05027
[2] F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969).
[3] B. Heinold, Sum list coloring and choosability (Ph.D. Thesis, Lehigh University, 2006).
[4] G. Isaak, Sum list coloring 2 × n arrays, Electron. J. Combin. 9 (2002) # N8. | Zbl 1003.05041
[5] G. Isaak, Sum list coloring block graphs, Graphs Combin. 20 (2004) 499-506. doi:10.1007/s00373-004-0564-1[Crossref] | Zbl 1053.05049
[6] A. Kemnitz, M. Marangio and M. Voigt, Bounds for the sum choice number, sub- mitted, 2015. | Zbl 1327.05111
[7] A. Kemnitz, M. Marangio and M. Voigt, Sum list colorings of small graphs, preprint, 2015. | Zbl 1338.05085
[8] A. Kemnitz, M. Marangio and M. Voigt, Sum list colorings of wheels, Graphs Com- bin. 31 (2015) 1905-1913. doi:10.1007/s00373-015-1565-y[Crossref] | Zbl 1327.05111
[9] E. Kubicka and A.J. Schwenk, An introduction to chromatic sums, in: A.M. Riehl, (Ed.), Proc. ACM Computer Science Conference (Louisville) (ACM Press, New York, 1989) 39-45. doi:10.1145/75427.75430[Crossref]
[10] M.A. Lastrina, List-coloring and sum-list-coloring problems on graphs (Ph.D. The- sis, Iowa State University, 2012).