Sum List Colorings of Wheels Artikel uri icon

Open Access

  • false

Peer Reviewed

  • true

Abstract

  • Let G = (V, E) be a simple graph and for every vertex v. V let L(v) be a set (list) of available colors. The graph G is called L-colorable if there is a proper coloring. of the vertices with phi(upsilon) is an element of L(v) for all v. V. Afunction f : V(G) -> Nis called a choice function of G and G is said to be f -list colorable if G is L-colorable for every list assignment L with | L(v)| = f (v) for all v. V. Set size(f) = Sigma(v is an element of V) f (v) and define the sum choice number chi(sc()G) as the minimum of size(f) over all choice functions f of G. It is easy to see that chi(sc() (G) <= | V| + | E| for every graph G and that there is a greedy coloring of G for the corresponding choice function f and every list assignment with | L(v)| = f (v). Therefore, a graph G with chi(sc() (G) = | V| + | E| is called sc-greedy. The concept of the sum choice number was introduced in 2002 by Isaak. In 2006, Heinold characterized the broken wheels (or fan graphs) with respect to sc-greedyness and obtained some results for wheels. In this paper we extend the result for wheels and provide a complete characterization of wheels concerning this property.

Veröffentlichungszeitpunkt

  • Januar 11, 2015