Sum List Edge Colorings of Graphs Artikel uri icon

Open Access

  • true

Peer Reviewed

  • true

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) = ∑ f(e) and define the sum choice index χ′ (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 χ′ (G) ≤ 1/2 ∑ d(v) . 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.

Veröffentlichungszeitpunkt

  • Januar 8, 2016