Vertex Coloring Optimal Sum vs Chromatic Number

Question

I am having trouble coming up with an example of when the number of colors used in the optimal solution of the sum coloring problem of a graph is strictly greater than the chromatic number of that graph.

Answer 1

The tree that is Figure 3.2 in this paper is an example. The chromatic number is $2$, but the lowest sum using only two colors is $21$. A sum of $19$ can be achieved with $3$ colors, using color $3$ for the root, and color $1$ for all leaves.

Answer 2

Consider the tree of order $8$ with degree sequence $(4,4,1,1,1,1,1,1).$ If we color it with colors $1$ and $2,$ the sum of the colors is $12.$ Using three colors, we can color the leaves with color $1$ and the vertices of degree $4$ with colors $2$ and $3,$ so that the sum of the colors is $11.$