Sum List Edge Colorings of Graphs

Arnfried Kemnitz; Massimiliano Marangio; Margit Voigt

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 3, page 709-722
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

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 -

References

top
  1. [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] Zbl1098.05027
  2. [2] F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969). 
  3. [3] B. Heinold, Sum list coloring and choosability (Ph.D. Thesis, Lehigh University, 2006). 
  4. [4] G. Isaak, Sum list coloring 2 × n arrays, Electron. J. Combin. 9 (2002) # N8. Zbl1003.05041
  5. [5] G. Isaak, Sum list coloring block graphs, Graphs Combin. 20 (2004) 499-506. doi:10.1007/s00373-004-0564-1[Crossref] Zbl1053.05049
  6. [6] A. Kemnitz, M. Marangio and M. Voigt, Bounds for the sum choice number, sub- mitted, 2015. Zbl1327.05111
  7. [7] A. Kemnitz, M. Marangio and M. Voigt, Sum list colorings of small graphs, preprint, 2015. Zbl1338.05085
  8. [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] Zbl1327.05111
  9. [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. [10] M.A. Lastrina, List-coloring and sum-list-coloring problems on graphs (Ph.D. The- sis, Iowa State University, 2012). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.