A Hajós-like theorem for weighted coloring.

The Hajós' Theorem (Wiss Z Martin Luther Univ Math-Natur Reihe, 10, pp 116-117, ) shows a necessary and sufficient condition for the chromatic number of a given graph $$G$$ to be at least $$k$$: $$G$$ must contain a $$k$$-constructible subgraph. A graph is $$k$$-constructible if it can be obtained from a complete graph of order $$k$$ by successively applying a set of well-defined operations. Given a vertex-weighted graph $$G$$ and a (proper) $$r$$-coloring $$c=\{C_1, \ldots , C_r\}$$ of $$G$$, the weight of a color class $$C_i$$ is the maximum weight of a vertex colored $$i$$ and the weight of $$c$$ is the sum of the weights of its color classes. The objective of the Weighted Coloring Problem [] is, given a vertex-weighted graph $$G$$, to determine the minimum weight of a proper coloring of $$G$$, that is, its weighted chromatic number. In this article, we prove that the Weighted Coloring Problem admits a version of the Hajós' Theorem and so we show a necessary and sufficient condition for the weighted chromatic number of a vertex-weighted graph $$G$$ to be at least $$k$$, for any positive real $$k$$. [ABSTRACT FROM AUTHOR]