A Stable Set Formulation for the Equitable Coloring Problem

References

• Bahiense L, Frota Y, Noronha TF, Ribeiro CC (2014) A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives. Discrete Appl. Math. 164(1):34–46.Crossref, Google Scholar
• Chen BL, Yen CH (2012) Equitable Δ-coloring of graphs. Discrete Math. 312(9):1512–1517.Crossref, Google Scholar
• Das SK, Finocchi I, Petreschi R (2006) Conflict-free star-access parallel memory systems. J. Parallel Distrib. Comput. 66(11):1431–1441.Crossref, Google Scholar
• Furmańczyk H (2005) The complexity of equitable vertex coloring of graphs. J. Appl. Comput. Sci. 13(2):95–107.Google Scholar
• Furmańczyk H (2006) Equitable coloring of graph products. Opuscula Math. 26(1):31–44.Google Scholar
• Furmańczyk H, Jastrzebski A, Kubale M (2016) Equitable coloring of graphs. Recent theoretical results and new practical algorithms. Arch. Control Sci. 26(3):281–295.Crossref, Google Scholar
• Gomes GCM, Guedes MR, dos Santos VF (2023) Structural parameterizations for equitable coloring: Complexity, FPT algorithms, and kernelization. Algorithmica 85(7):1912–1947.Crossref, Google Scholar
• Hajnal A, Szemerédi E (1970) Proof of a conjecture of P. Erdos. Erdos P, Renyi A, Sos VT, eds. Combinatorial Theory and its Application (North Holland Publishing Company, Amsterdam), 601–623.Google Scholar
• Held S, Cook W, Sewell EC (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4:363–381.Crossref, Google Scholar
• Kierstead HA, Kostochka AV, Mydlarz M, Szemerédi E (2010) A fast algorithm for equitable coloring. Combinatorica 30(2):217–224.Crossref, Google Scholar
• Lai X, Hao JK, Glover F (2015) Backtracking based iterated tabu search for equitable coloring. Engrg. Appl. Artificial Intelligence 46(A):269–278.Crossref, Google Scholar
• Lih KW (2013) Equitable coloring of graphs. Du DZ, Pardalos PM, eds. Handbook of Combinatorial Optimization (Springer, Berlin, Heidelberg) 1199–1248.Crossref, Google Scholar
• Mehrotra A, Trick MA (1996) A column generation approach for graph coloring. INFORMS J. Comput. 8(4):344–354.Link, Google Scholar
• Méndez-Díaz I, Nasini G, Severín D (2014a) A tabu search heuristic for the equitable coloring problem. Fouilhoux P, Gouveia L, Mahjoub A, Paschos V, eds. Internat. Sympos. Combinatorial Optim. LNCS, vol. 8596 (Springer, Berlin, Heidelberg), 347–358.Crossref, Google Scholar
• Méndez-Díaz I, Nasini G, Severín D (2014b) A polyhedral approach for the equitable coloring problem. Discrete Appl. Math. 164:413–426.Crossref, Google Scholar
• Méndez-Díaz I, Nasini G, Severín D (2015) A DSATUR-based algorithm for the equitable coloring problem. Comput. Oper. Res. 57:41–50.Crossref, Google Scholar
• Meyer W (1973) Equitable coloring. Amer. Math. Monthly 80(8):920–922.Crossref, Google Scholar
• Olariu EF, Frăsinaru C (2022) Improving lower bounds for equitable chromatic number. Comput. Oper. Res. 143:105790.Crossref, Google Scholar
• Olariu EF, Frăsinaru C (2026) A stable set formulation for the Equitable Coloring Problem. INFORMS J. Comput. https://doi.org/10.1287/ijoc.2025.1294.cd, https://github.com/INFORMSJoC/2025.1294.Crossref, Google Scholar
• Sun W, Hao JK, Lai X, Wu Q (2017) On feasible and infeasible search for equitable graph coloring. GECCO ‘17: Proc. Genetic Evolutionary Computat. Conf. (Association for Computing Machinery, New York), 369–376.Google Scholar
• Sun W, Hao JK, Wang W, Wu Q (2020) Memetic search for the equitable coloring problem. Knowl. Based Systems 188:105000.Crossref, Google Scholar
• Wang W, Hao JK, Wu Q (2018) Tabu search with feasible and infeasible searches for equitable colouring. Engrg. Appl. Artificial Intelligence 71:1–14.Crossref, Google Scholar