Contractions and minimal k-colorability (Q916670)

Coloring the vertex set of a graph G with positive integers we can define the chromatic sum \(\Sigma\) (G) of G. It is the minimum sum of colors on all vertices of G. The strength of G is the largest integer that occurs as color in every coloring whose total sum is equal \(\Sigma\) (G). The main results are given by the following theorems: Theorem 1. Every tree of strength s has at least \(t(s)=((2+\sqrt{2})^{s-1}-(2- \sqrt{2})^{s-1})/\sqrt{2}\) vertices. Moreover, for every \(s\geq 2\) this lower bound is sharp and the smallest tree \(T_ s\) is unique. Theorem 2. For every natural number \(s\geq 3\), there are two trees \(T_ s\) and \(R_ s\) of strength s, such that every tree of strength at least s is contractible to \(T_ s\) or \(R_ s.\) The trees \(T_ s\) and \(R_ s\) from theorems 1 and 2 are rooted trees described recursively. E.g. \(R_ s(s>1)\) we obtain from s copies of \(R_ 1\), s-1 copies of \(R_ 2,...,2\) copies of \(R_{s-1}\) by joining their roots with a new additional vertex (the root of \(R_ s)\). The tree \(R_ 1\) is just one vertex. Some open problems are given in the concluding remarks.