A Stable Set Formulation for the Equitable Coloring Problem

Some equity constraints on the coloring classes of a classical coloring of the vertices of a graph give rise to the equitable coloring: the number of vertices colored with each color differs by at most one. The least number of colors for which a graph has such an equitable coloring is called the equitable chromatic number. In this paper a new integer programming model is introduced based on a stable set formulation for the decision version of the Equitable Coloring Problem. This new formulation is integrated into two Binary Search-like algorithms, the efficiency of which we have tested on thirty-two instances from literature. The numerical results show that this new approach was able to improve the known lower bounds of equitable chromatic number for two thirds of the tested instances and found the equitable coloring number for two instances.

History: Accepted by Andrea Lodi, Design & Analysis of Algorithms–Discrete.

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1294) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1294). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.