Data: 15/10/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: The (Parameterized) Complexity of Equitable Coloring
Palestrante: Guilherme Gomes (UFMG)


Abstract: A graph is equitably k-colorable if there is a proper coloring where the number of times two colors are used differ by at most one, and the Equitable Coloring problem asks whether or not a graph can be equitably k-colored. While Vertex Coloring is solvable in polynomial time in a multitude of graph classes, Equitable Coloring is NP-complete even on very restricted classes, such as cographs and interval graphs. In this talk, we discuss some recent advances on the complexity of Equitable Coloring on graph classes and its parameterized complexity. We begin by presenting NP-hardness reductions for some subclasses of chordal graphs, a complexity dichotomy for interval graphs, and a polynomial time algorithm for unipolar graphs. Afterwards, we study the complexity of the problem under widely used structural parameterizations.
In this setting, we show how the result on unipolar graphs can be generalized to FPT algorithms for cluster +kv graphs and co-cluster +kv graphs when parameterized by k. We also present other tractability and intractability results, as well as a novel cubic kernel when parameterized by the maximum leaf number.

(Joint work with Matheus Guedes, Carlos Lima, and Vinicius dos Santos)