Let\(G=(V,E)\) be a simple graph and for every vertex\(v\in V\) let\(L(v)\) be a set (list) of available colors. The graph\(G\) is called\(L\)-colorable if there is a proper coloring\(\varphi \) of the vertices with\(\varphi (v)\in L(v)\) for all\(v\in V\). A function\(f:V(G) \rightarrow \mathbb N\) is called achoice 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\in V\). Set\({{\mathrm{size}}}(f)=\sum \nolimits _{v\in V} f(v)\) and define thesum choice number\(\chi _{sc}(G)\) as the minimum of\({{\mathrm{size}}}(f)\) over all choice functions\(f\) of\(G\). It is easy to see that\(\chi _{sc}(G)\le |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.

Authors and Affiliations

1. Computational Mathematics, Technical University Braunschweig, 38023, Braunschweig, Germany

   Arnfried Kemnitz & Massimiliano Marangio

2. Faculty of Information Technology and Mathematics, University of Applied Sciences, Friedrich-List-Platz 1, 01069, Dresden, Germany

   Margit Voigt

Corresponding author

Correspondence toMargit Voigt.

Reprints and permissions