Sum List Edge Colorings of Graphs

Arnfried Kemnitz, Massimiliano Marangio, and Margit Voigt. "Sum List Edge Colorings of Graphs." Discussiones Mathematicae Graph Theory 36.3 (2016): 709-722. <http://eudml.org/doc/285732>.

@article{ArnfriedKemnitz2016,
abstract = {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.},
author = {Arnfried Kemnitz, Massimiliano Marangio, Margit Voigt},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {sum list edge coloring; sum choice index; sum list coloring; sum choice number; choice function; line graph; sum list edge-coloring},
language = {eng},
number = {3},
pages = {709-722},
title = {Sum List Edge Colorings of Graphs},
url = {http://eudml.org/doc/285732},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Arnfried Kemnitz
AU - Massimiliano Marangio
AU - Margit Voigt
TI - Sum List Edge Colorings of Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 709
EP - 722
AB - 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.
LA - eng
KW - sum list edge coloring; sum choice index; sum list coloring; sum choice number; choice function; line graph; sum list edge-coloring
UR - http://eudml.org/doc/285732
ER -