Sum List Edge Colorings of Graphs

• Autorzy: Arnfried Kemnitz , Massimiliano Marangio , Margit Voigt
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

sum list edge coloring; sum choice index; sum list coloring; sum choice number; choice function; line graph

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 3
• Strony: 709-722

Daty

wydano

2016-08-01

otrzymano

2014-12-18

poprawiono

2015-11-02

zaakceptowano

2015-11-02

online

2016-07-06

Twórcy

autor

Arnfried Kemnitz

• Computational Mathematics Technical University Braunschweig Pockelsstraße 14, 38 106 Braunschweig, Germany

autor

Massimiliano Marangio

• Computational Mathematics Technical University Braunschweig Pockelsstraße 14, 38 106 Braunschweig, Germany

autor

Margit Voigt

• Faculty of Information Technology and Mathematics University of Applied Sciences Friedrich-List-Platz 1, 01 069 Dresden, Germany

Bibliografia

• [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[Crossref]
• [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[Crossref]
• [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[Crossref]
• [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[Crossref]
• [10] M.A. Lastrina, List-coloring and sum-list-coloring problems on graphs (Ph.D. The- sis, Iowa State University, 2012).

Identyfikatory

DOI

10.7151/dmgt.1884