Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: sum choice index

Sortuj według:

Ogranicz wyniki do:

Sum List Edge Colorings of Graphs

100%

Kemnitz A., Marangio M., Voigt M.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 3

709-722

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Kemnitz A.

1 Marangio M.

1 Voigt M.

1 2016

Wyniki wyszukiwania

Sum List Edge Colorings of Graphs