MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEWeighted Coloring par Julio Araujo
Date : | 23/11/10 | Time : | 10:30 | Location : | Galois Coriolis |
Â' 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.
Page des séminaires
|