https://hal.inria.fr/hal-00773410Araujo, JulioJulioAraujoParGO - Parallelism, Graphs and Optimization Research Group - UFC - Universidade Federal do Ceará = Federal University of CearáCOATI - Combinatorics, Optimization and Algorithms for Telecommunications - CRISAM - Inria Sophia Antipolis - Méditerranée - Inria - Institut National de Recherche en Informatique et en Automatique - Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués - I3S - Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis - UNS - Université Nice Sophia Antipolis (1965 - 2019) - COMUE UCA - COMUE Université Côte d'Azur (2015-2019) - CNRS - Centre National de la Recherche Scientifique - UCA - Université Côte d'AzurLinhares Sales, ClaudiaClaudiaLinhares SalesParGO - Parallelism, Graphs and Optimization Research Group - UFC - Universidade Federal do Ceará = Federal University of CearáA Hajós-like theorem for weighted coloringHAL CCSD2013[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]Araujo, Julio2013-01-14 00:52:002023-03-24 14:52:562013-01-14 08:56:07enJournal articleshttps://hal.inria.fr/hal-00773410/document10.1007/s13173-012-0098-yapplication/pdf1The Hajós' Theorem (Wiss Z Martin Luther Univ Math-Natur Reihe, 10, pp 116-117, 1961) 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\$.