Sum List Edge Colorings of Graphs

Kemnitz, Arnfried  ; Marangio, Massimiliano ; Voigt, Margit

Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 709-722

Résumé

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.

Détail

Keywords: sum list edge coloring, sum choice index, sum list coloring, sum choice number, choice function, line graph