Kernelization results for Equitable Coloring
Guilherme C. M. Gomes, Vinícius Fernandes dos Santos · Procedia Computer Science · 2021
An n-vertex graph is equitably k-colorable if there is a proper coloring of its vertices such that each color is used either [n/k] or [n/k] times. While classic Vertex Coloring is fixed parameter tractable under well established parameters such as pathwidth and feedback vertex set, equitable coloring is W[1]-hard. Little is known, however, about kernelization aspects of Equitable Coloring. In this work, we begin this investigation by first presenting a linear kernel for the parameter distance to clique, which contrasts with the quadratic kernel for Vertex Coloring under the same parameterization. Our main technical contribution is an OR-cross-composition from Multicolored Clique to Number List Coloring parameterized by vertex cover and number of colors which, along with two simple PPT reductions, implies that Equitable Coloring has no polynomial kernel under the same parameterization unless NP ⊆ coNP/poly.