PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 3 | 709-722
Tytuł artykułu

Sum List Edge Colorings of Graphs

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
36
Numer
3
Strony
709-722
Opis fizyczny
Daty
wydano
2016-08-01
otrzymano
2014-12-18
poprawiono
2015-11-02
zaakceptowano
2015-11-02
online
2016-07-06
Twórcy
  • Computational Mathematics Technical University Braunschweig Pockelsstraße 14, 38 106 Braunschweig, Germany, a.kemnitz@tu-bs.de
  • Computational Mathematics Technical University Braunschweig Pockelsstraße 14, 38 106 Braunschweig, Germany, m.marangio@tu-bs.de
autor
  • Faculty of Information Technology and Mathematics University of Applied Sciences Friedrich-List-Platz 1, 01 069 Dresden, Germany, mvoigt@informatik.htw-dresden.de
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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1884
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.