Data: 18/12/2019

Título:  Recent algorithmic results on equitable coloring

Palestrantes: Prof. Vinícius Santos, UFMG. 

Data: 18 de Dezembro de 2019, 11 h.
Local: Sala 407, Bloco H, Campus Gragoatá, UFF.

Resumo: A proper coloring of a graph is a labeling of its vertex set such that adjacent vertices receive disctinct labels. Many problems can be modelled using graph colorings, such as scheduling and task assignment problems. On such problems, one may be interested in the case where the coloring is balanced in the following sense: the number of times two different colors occurs in the graph can differ by at most one. Such proper colorings are called equitable colorings.

Similarly to the traditional version, determining whether a graph has an equitable coloring with a given amount of colors is a computationally hard problem. However, for many settings where coloring is tractable, the problem becomes hard for the equitable version. In this talk we present some recent advances on this problem, such as polynomial time algorithms for some special cases and positive and negative results concerning the parameterized complexity of the problem.

Obs: joint work with Matheus Guedes and Guilherme Gomes.

Confira aqui a apresentação.