Aug 2026· INFORMS journal on computing· 0 citations· 16 references
Abstract
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/ .
Given a graph $G=(V,E)$, a (proper) $k$-coloring for $G$ is a vertex coloring with $k$ colors such that every two adjacent vertices receive different colors. Suppose that the vertex set $V$ is partitioned into some groups, a proper coloring is called fair if for every color class, the difference between the number of vertices in any two groups does not exceed a given threshold. In this paper, we investigate the parameterized complexity of the fair coloring problem with respect to the structural parameters of the input graph. In particular, we prove that the problem is W[1]-hard with respect to the number of groups for forests and also graphs of modular-width two, even when the number of colors is equal to two. On the positive side, we prove that when the number of colors is equal to two, then the problem is FPT with respect to neighborhood diversity of the input graph. Moreover, in general, the problem is FPT with respect to neighborhood diversity and the number of groups. As a by-product, we prove that unary vector bin packing problem is W[1]-hard with respect to the dimension.
R. Javadi, Hossein Shokouhi· arXiv.org· 0 citations
Coloring the vertices, edges or faces of a graph so that no two adjacent elements share a label is among the oldest problems in graph theory, and one of the few whose reach extends into exam timetables and wireless spectrum allocation as it does into pure combinatorics. This survey draws together the problem’s theoretical core – vertex, edge, face, list and total coloring – with the algorithms built to solve it and the industries that now depend on those algorithms. Because coloring is NP-hard, we trace the field’s progression from exact and greedy methods (Welsh-Powell, DSATUR, backtracking) through metaheuristics that trade optimality for scale (genetic algorithms, tabu search, simulated annealing, ant colony and artificial bee colony optimization), to the graph neural network and quantum-inspired solvers that have emerged in recent years. Rather than treating theory, algorithms and applications as separate literatures, we connect them directly: each application – examination and crew scheduling, frequency assignment, compiler register allocation, cartographic map coloring – is traced back to the specific coloring variant and algorithm family the literature actually uses, while the algorithm families themselves are compared head-to-head on complexity, solution quality and scalability rather than catalogued one at a time. This comparative structure, together with its coverage of recent learning-based solvers, is what distinguishes this survey from the standard references on the subject. We close by outlining where the field’s open problems remain, from long standing conjectures to the still-unanswered question of whether learned heuristics can match classical methods at real-world scale.
Jisha Ann Abraham, C. Wilfred, Thomaskutty Stephen· International journal of com...· 0 citations
A graph has an
‐coloring
if there exists an assignment from the vertices to subsets of with size such that adjacent vertices are assigned disjoint subsets. Odd girth at least is a necessary condition for a graph to have a ‐coloring. Chen and Raspaud conjectured a tight upper bound on the maximum average degree of a graph with odd girth at least that guarantees a ‐coloring. Namely, they conjectured that every graph with odd girth at least and maximum average degree less than has a ‐coloring. This conjecture is true for ; when , computers were used to perform case analysis. The main result of this paper confirms the conjecture for the next open case () without the use of computers. Moreover, our approach yields simpler, computer‐free proofs for previously known cases ().
Ilkyoo Choi· Journal of Graph Theory· 1 citation· ⚡1
A suite of fast randomized distributed algorithms representing varying points on this tradeoff are presented, analyze their properties, and study their time complexity in the sequential, CONGEST and Congested Clique models.
The Ramsey number $R(m,n)$ is the smallest order at which every red-blue edge coloring of a complete graph must contain a blue clique (a complete subgraph) of size $m$ or a red clique of size $n$. Determining these numbers exactly is extremely hard, and even certifying a lower bound requires exhibiting an explicit coloring that avoids both cliques. We develop an integer programming framework for certifying such lower bounds, restricting the search to circulant graphs, whose rotational symmetry lets us reformulate the problem in a projected distance space, reducing the number of binary variables from quadratic to linear in the graph order. We strengthen this projected model through coefficient reduction and solve it with a branch-and-cut algorithm whose separation routine exploits the common neighborhood structure of circulant graphs, combining heuristic and exact maximum-clique algorithms. In an extensive computational campaign on circulant graphs with up to 410 vertices, we improve the best lower bounds previously obtained by other methods by up to 11 points for 25 values of $R(3,n)$ with $24\le n\le49$ and $n\neq27$, each backed by an explicit graph certificate that can be independently verified with a stand-alone exact clique solver. To the best of our knowledge, our method also provides the first reproducible optimization-based procedure for certifying circulant Ramsey numbers $R_C(m,n)$, which we use to establish eight new values of $R_C(3,n)$ with $13\le n\le20$. Our framework, graph certificates, and stand-alone checker are provided as supplementary material to support independent verification and reuse.
Stefano Coniglio, Fabio Furini, I. Ljubić et al.· 0 citations
We study graph coloring with color preferences, in which each vertex ranks the available colors. In addition to assigning different colors to adjacent vertices, we require the coloring to be stable: no group of vertices can cyclically exchange their assigned colors so that each strictly prefers its new color to its original one. We define the stable chromatic number $\chi_\mathrm{stable}(G)$ of a graph $G$ as the minimum integer $k$ such that every preference profile admits a stable $k$-coloring of $G$. We establish several upper and lower bounds. In particular, for any acyclic orientation of the edges of $G$, the largest number of vertices reachable from a vertex by directed paths, including the vertex itself, is an upper bound on $\chi_\mathrm{stable}(G)$. This shows that $\chi_\mathrm{stable}(G)$ is well-defined. We also show that $O(t \log (1+n/t))$ colors suffice for an $n$-vertex graph $G$ of treewidth $t$, and complement this with a lower bound in terms of the Grundy number. Turning to the problem of finding a minimum stable coloring for a given profile, we show that stable $2$-colorability is polynomial-time solvable, whereas stable $k$-colorability is NP-complete for every fixed $k\ge 3$. Using the treewidth bound, we give a fixed-parameter tractable algorithm parameterized by treewidth.
Tomohiro Koana, Y. Oh, Hirotaka Yoneda· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
