Recent algorithmic results on equitable coloring

Speaker: Vinicius Santos, UFMG.

Date: 18 dec 2019, 11h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: A proper coloring of a graph is a labeling of its vertex set such that adjacent vertices receive distinct 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.

This is joint work with Matheus Guedes and Guilherme Gomes.