Comparison of sum choice number with chromatic sum (Q2032707)

For a simple graph \(G = (V(G),E(G))\), with both \(V(G)\) and \(E(G)\) finite sets, a proper coloring of \(G\) is here a map \(\phi : V(G) \rightarrow \{1,2,3,\ldots\} = \mathbb{N}\) such that every pair of adjacent vertices receive distinct colors. The chromatic sum \(\Sigma(G)\) of \(G\) is the minimum of the sum of colors of the vertices \(\sum_{u\in V(G)}\phi(u)\) among all proper colorings \(\phi\) of \(G\). Suppose we have a list/set \(L(u)\) of available colors for every vertex \(u\in V(G)\). The graph \(G\) is \(L\)-colorable if there is a proper coloring \(\phi\) of \(G\) with \(\phi(u)\in L(u)\subseteq \mathbb{N}\) for each \(u\in V(G)\). A function \(f : V(G) \rightarrow \mathbb{N}\) is a choice function of \(G\) if \(G\) is \(L\)-colorable for every list assignment \(L\) with \(|L(u)| = f(u)\) for each \(u\in V(G)\). For a choice function \(f\) let \(\operatorname{size}(f) = \sum_{u\in V(G)}f(u)\) and define the sum choice number \(\chi_{sc}(G)\) as the minimum of \(\operatorname{size}(f)\) among all choice functions \(f\) of \(G\). This article investigates two functions \[ g(n) := \max_{\Sigma(G) = n}\frac{\chi_{sc}(G)}{\Sigma(G)} \text{ and } h(n) := \max_{|V(G)|= n}\frac{\chi_{sc}(G)}{\Sigma(G)}. \] By definition one has that \(\Sigma(G)\leq \chi_{sc}(G)\) and a greedy coloring shows that \(\chi_{sc}(G) \leq |V(G)| + |E(G)| := \mathrm{GB}(G)\), the greedy bound of \(G\). This article derives some upper and lower bounds for the functions \(g\) and \(h\) as well as some exact values of both \(\Sigma(G)\) and \(\chi_{sc}(G)\) for some specific known graphs \(G\), like the complete, cycle and star graphs. The partial results presented support the conjectures that both \(g\) and \(h\) are \(\Theta(\log(n))\)-functions for large \(n\).