Given an undirected vertex-weighted graph G = (V, E, w), a vertex
coloring of G is a partition of V into independent sets, or color classes.
The weight of
a vertex coloring of G is defined as the sum of the weights of its color
classes, where the
weight of a color class is the weight of a heaviest vertex belonging to it.
In the Weighted
Coloring problem, we want to determine the minimum weight among all vertex
colorings of
G. This problem is NP-hard since it generalizes the Vertex Coloring problem.
When the weights
are all equal to one, then solving this problem is equivalent to determining
the chromatic number
of the input graph.

In this talk, we will present some known results in the literature about
Weighted Coloring and
some new ones like a version of the HajÃ'³s' Theorem for it.

This is a joint work with
Claudia Linhares Sales.