Geodesic
Sum List Edge Colorings of Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 709-722.

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

Let G = (V,E) be a simple graph and for every edge ℯ∈ 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(ℯ ) ∈ L( ℯ ) for all ℯ∈ 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( ℯ )| = f( ℯ ) for all ℯ∈ E. Set size(f) = Σ_ℯ∈ 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.
Keywords: sum list edge coloring, sum choice index, sum list coloring, sum choice number, choice function, line graph 
@article{DMGT_2016_36_3_a14,
     author = {Kemnitz, Arnfried and Marangio, Massimiliano and Voigt, Margit},
     title = {Sum {List} {Edge} {Colorings} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {709--722},
     publisher = {mathdoc},
     volume = {36},
     number = {3},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a14/}
}
TY  - JOUR
AU  - Kemnitz, Arnfried
AU  - Marangio, Massimiliano
AU  - Voigt, Margit
TI  - Sum List Edge Colorings of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 709
EP  - 722
VL  - 36
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a14/
LA  - en
ID  - DMGT_2016_36_3_a14
ER  - 
%0 Journal Article
%A Kemnitz, Arnfried
%A Marangio, Massimiliano
%A Voigt, Margit
%T Sum List Edge Colorings of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 709-722
%V 36
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a14/
%G en
%F DMGT_2016_36_3_a14
Kemnitz, Arnfried; Marangio, Massimiliano; Voigt, Margit. Sum List Edge Colorings of Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 709-722. http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a14/

[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] 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.

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

[6] A. Kemnitz, M. Marangio and M. Voigt, Bounds for the sum choice number, sub- mitted, 2015.

[7] A. Kemnitz, M. Marangio and M. Voigt, Sum list colorings of small graphs, preprint, 2015.

[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

[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

[10] M.A. Lastrina, List-coloring and sum-list-coloring problems on graphs (Ph.D. The- sis, Iowa State University, 2012).