Contractions and minimalk-colorability

Coloring the vertex set of a graphG with positive integers, thechromatic sum (G) ofG is the minimum sum of colors in a proper coloring. Thestrength ofG is the largest integer that occurs in every coloring whose total is(G). Proving a conjecture of Kubicka and Schwenk, we show that every tree of strengths has at least ((2 + ) ^s–1 – (2 – ) ^s–1)/ vertices (s 2). Surprisingly, this extremal result follows from a topological property of trees. Namely, for everys 3 there exist precisely two treesT _s andR _s such that every tree of strength at leasts is edge-contractible toT _s orR _s .