betaFeedback

WorksComputer Science

Scone: Symmetry-aware Neural Combinatorial Optimization for Graph Coloring

Abstract

Graph coloring, which entails assigning colors to nodes such that no adjacent nodes have the same color, is a fundamental combinatorial optimization problem. In general, however, finding a node coloring with no monochromatic edges given a fixed palette is NP-hard. This motivates learning-based methods that can learn to exploit recurring structure across instances to efficiently produce high-quality colorings. Crucially, the validity of a coloring is invariant to permutations of the colors, and we show that exploiting this symmetry reduces the size of the effective state space over which the model has to learn its policy. At the same time, the coloring algorithm must be able to break some symmetries, for example to assign different colors to two adjacent nodes belonging to the same automorphism orbit. In this paper, we introduce Scone, a model that uses a color-equivariant graph neural network to construct colorings sequentially, allowing information from previous assignments to propagate and break node symmetries. Scone achieves perfect solution quality with low inference times across several graph coloring tasks, including on sudoku_extreme and register allocations, and showcases generalization to graph families not encountered during training.

Introduction

Graph coloring is a fundamental combinatorial optimization problem, which, given a graph and a palette of colors, asks for an assignment of colors to the nodes of the graph such that adjacent nodes receive different colors. Given a palette of kk colors, deciding whether such an assignment exists is NP-complete for every fixed k≥3k \ge3 [22]. Moreover, computing the smallest number of colors required to obtain a conflict-free assignment, known as the chromatic number, is NP-hard.

Graph coloring has applications in several practical domains, such as register allocation, where a compiler has to choose how to assign the variables of a program to the computer registers [17], and timetabling problems, where conflicting activities must occupy distinct timeslots [71, 16]. Sudoku puzzles can also be seen as graph coloring instances, with cells represented as nodes and digits as colors [30].

Traditional exact approaches include integer programming [48], as well as SAT and constraint satisfaction problem (CSP) solvers [31]. Moreover, classical heuristics, which are generally faster but provide no guarantee of finding a valid coloring, include constructive algorithms such as greedy coloring [71] and DSATUR [13], as well as local-search methods [29, 46].

Intuitively, when instances are drawn from a distribution or feature recurring structure, machine-learning-based algorithms can learn to exploit these regularities and produce high-quality solutions efficiently. More generally, neural combinatorial optimization uses learned models as heuristics for constrained optimization problems like the traveling salesman [11, 35] and knapsack [20]. When trained on instance distributions, these models amortize the cost of learning a heuristic and enable fast inference on new instances [12].

Related Work. For graph coloring, neural approaches can optimize instances directly or learn across a distribution. PI-SAGE [59] casts coloring as unsupervised node classification, using a graph neural network (GNN) to produce soft color assignments, which are then rounded. Building on PI-SAGE, Vanderschüt & Weber (2026) improve approximate kk-coloring using recursive warm starts obtained from (k−1)(k-1)-colorings. ROS [54] similarly relaxes assignments to continuous ones, optimizes a continuous objective, and samples discrete solutions. Other methods learn general procedures across instances. ANYCSP ([63]) trains a GNN with reinforcement learning for solving general CSPs by performing global stochastic updates. Similarly, CONsFORMER ([73]) trains a Transformer to improve complete assignments using differentiable relaxations of the constraints, as a learned form of local search. Le et al. [39] learn color representations with a contrastive loss and decode them by clustering. Li et al. [43] also propose a color-equivariant model using restricted linear equivariant updates, but predict all node colors simultaneously, without conditioning each assignment on previous ones as in sequential decoding. Instead, Watkins et al. [70] propose a sequential constructive heuristic that learns node selection, while a fixed rule assigns the lowest permissible color. See Appendix § 13 for additional related work.

Graph tasks often exhibit symmetries ([24]). Most commonly, if two graphs are isomorphic via a node permutation, node-level outputs should permute accordingly. In graph coloring, applying the same node permutation to a graph and to a valid coloring preserves validity. Importantly, however, an individual coloring isn’t invariant under node permutations, since nodes in the same automorphism orbit may receive different colors. A solver must therefore be able to break node symmetries. Moreover, graph coloring exhibits a symmetry over its output. Color labels are interchangeable, since permuting them transforms any coloring into an equivalent one. These observations suggest that a learned solver should exploit both forms of symmetry to learn efficiently.

Contributions We introduce SCONE (Symmetry-aware COloring via Neural Equivariance), a model that constructs colorings sequentially, one node at a time. At each step, it takes as input the current partial coloring, allowing information from previous assignments to propagate through the graph, which distinguishes any nodes that were previously symmetric. Node colors are scored by a color-equivariant GNN, so relabeling the colors permutes the predictions accordingly without changing the behavior of the model. We show theoretically that equivariance reduces the state space that the model must learn (Theorem 1), and that sequential decoding yields expressive models (Theorems 3, 4). In summary, SCONE combines sequential predictions, equivariance and classical search for expressivity and efficiency. We evaluate SCONE on real-world coloring applications, including Sudoku, register allocation, and exam timetabling. Here, it achieves state-of-the-art solution quality among neural methods, achieving the best solution quality while also having the lowest solve times.

Preliminaries

A graph is a tuple G=(VG,EG)G = (V_G, E_G), where VG={1,…,∣VG∣}V_G = \{1, \ldots, |V_G|\} is a set of nodes and EG⊆{{u,v}:u,v∈VG,u≠v}E_G \subseteq\{\{u,v\} : u,v \in V_G, u \ne v\} is a set of undirected edges. We denote by NG(u)N_G(u) the set of neighbors of uu.

Graph coloring Let C={1,…,k}\mathcal{C} = \{1, \ldots, k\} be a palette of kk colors, and let ε\varepsilon denote the absence of a color. A partial kk-coloring of GG is a map c:VG→C∪{ε}c: V_G \to\mathcal{C} \cup\{\varepsilon\}. We refer to G=(G,c)G = (G,c) as a kk-coloring instance. A complete coloring c∗:VG→Cc^*: V_G \to\mathcal{C} is a proper coloring if c∗(u)≠c∗(v) ∀{u,v}∈EGc^*(u) \ne c^*(v) \ \forall\{u,v\} \in E_G. It is a valid solution of (G,c)(G,c) if it is proper and extends the coloring cc, i.e., c(u)≠ε⇒c∗(u)=c(u)c(u) \ne\varepsilon\Rightarrow c^*(u) = c(u). A graph is kk-colorable if it has a proper kk-coloring, and its chromatic number χ(G)\chi(G) is the smallest such kk.

Groups and permutations For group Γ\Gamma, let γ⋅x\gamma\cdot x be the action of γ∈Γ\gamma\in\Gamma on xx. Its Γ\Gamma-orbit is Γ⋅x={γ⋅x:γ∈Γ}\Gamma\cdot x = \{\gamma\cdot x : \gamma\in\Gamma\}, and X/Γ\mathcal{X}/\Gamma denotes the set of orbits. A function f:X→Yf: \mathcal{X} \to\mathcal{Y} is Γ\Gamma-equivariant if f(γ⋅x)=γ⋅f(x)f(\gamma\cdot x) = \gamma\cdot f(x) for all γ∈Γ\gamma\in\Gamma and x∈Xx \in\mathcal{X}. We denote by SmS_m the group of permutations of {1,…,m}\{1,\ldots,m\}. For τ∈Sm\tau\in S_m, let Pτ∈{0,1}m×mP_\tau\in\{0,1\}^{m \times m} be its permutation matrix, such that (Pτx)i=xτ−1(i)(P_\tau x)_i = x_{\tau^{-1}(i)}. A node permutation π\pi acts on graphs by relabeling their nodes as π⋅G=(VG,{{π(u),π(v)}:{u,v}∈EG})\pi\cdot G = (V_G, \{\{\pi(u),\pi(v)\} : \{u,v\} \in E_G\}), and on a coloring as (π⋅c)(π(u))=c(u),∀u(\pi\cdot c)(\pi(u)) = c(u), \forall u. Two colorings that are isomorphic if one is obtained from the other by such a node permutation π\pi, written (G,c)≃(G′,c′)(G,c) \simeq(G',c'). If such a π\pi satisfies π(u)=u′\pi(u) = u', then u∈VGu \in V_G and u′∈VG′u' \in V_{G'} have the same rooted isomorphism type. We denote by Aut⁡(G,c)={π:π⋅G=G,π⋅c=c}\operatorname{Aut}(G,c) = \{\pi: \pi\cdot G = G, \pi\cdot c = c\} the automorphism group of (G,c)(G,c). Its orbits on VGV_G are called node orbits. Intuitively, two nodes share an orbit if an isomorphism from (G,c)(G,c) to itself maps one to the other.

Graph Coloring and Symmetries

Our goal is to design a machine learning model that colors a graph from a fixed palette while minimizing monochromatic edges, ideally producing a proper coloring. This requires exploiting the symmetries of the task for sample efficiency, while breaking them when necessary for expressivity.

Node permutation symmetries and when to break them

Consider a graph coloring instance (G,c)(G,c) and a valid solution (i.e., a valid coloring completing cc) c∗:VG→Cc^*: V_G \to C. Then, if another graph (G′,c′)(G',c') is isomorphic to (G,c)(G,c) via an isomorphism π\pi, the coloring π⋅c∗\pi\cdot c^* is a valid solution for (G′,c′)(G',c'). We therefore want to use an architecture that is equivariant to permutations of the nodes, like a message-passing GNN [24].

The most immediate strategy for graph coloring with a model is to treat color assignment as a multiclass classification task with labels in CC. We would predict the color scores simultaneously for each node, and then select the argmax color for each node independently from each other, as if it was a node classification task. However, as noted also in [43], this strategy has a fundamental limitation, as nodes in the same node orbit of (G,c)(G,c) are assigned the same color even if neighboring.

Consider, for example, the adjacent nodes v1v_1 and v2v_2 in Figure 1 (a). Since they belong to the same orbit, any node-equivariant predictor must assign them the same vector of color scores, even if it can distinguish arbitrary rooted-graph isomorphism types. Therefore, an adversary can always break any score ties so that these nodes are assigned the same color, thus failing to yield a proper coloring.

Figure 1. (a) Nodes v1v_1 and v2v_2 are symmetric and thus indistinguishable, so a deterministic model that predicts colors simultaneously for each node must assign them the same color, even if adjacent. (b) SCONE sequentially colors one node at a time, conditioned on previous assignments. Once v1v_1 has been colored, v2v_2 can be distinguished from it, allowing the model to assign a distinct color to v2v_2.

Therefore, although the predictor itself remains permutation-equivariant, the decoding procedure must be able to break symmetries. We do so by constructing the solution sequentially, coloring one node at a time and recomputing the scores after every assignment, see Figure 1 (b). When automorphic nodes are tied, selecting any one of them breaks the symmetry of the resulting state, allowing previously indistinguishable nodes to become distinguishable. In particular, given the graph and a partial coloring, the model produces color scores to every uncolored node, selects one node, and updates the coloring by assigning it the highest-scoring color. The process ends when all nodes are colored.

More formally, given a kk-coloring instance (G,c0)(G,c_0), we define the state space S(G,c0)S_{(G,c_0)} as the set of instances (up to isomorphism) that can be reached by coloring some uncolored nodes of GG, and the set of extendable states S(G,c0)+S^+_{(G,c_0)} as states that can lead to a proper coloring c∗c^* of (G,c0)(G,c_0), i.e.

S(G,c0)={(G,c):c0(v)≠⊥⇒c(v)=c0(v) ∀v∈VG}/∼S_{(G,c_0)}=\{(G,c):c_0(v)\ne\bot\Rightarrow c(v)=c_0(v)\ \forall v\in V_G\}/\sim
S(G,c0)+={(G,c):∃ valid solution c∗ of (G,c0) s.t. c(v)≠⊥⇒c(v)=c∗(v) ∀v∈VG}/∼.S^+_{(G,c_0)}=\{(G,c):\exists\text{ valid solution }c^*\text{ of }(G,c_0)\text{ s.t. }c(v)\ne\bot\Rightarrow c(v)=c^*(v)\ \forall v\in V_G\}/\sim.

From each state (G,c)∈S(G,c0)(G,c)\in S_{(G,c_0)}, the policy assigns to each uncolored node a score for each color. Based on these scores the policy selects a single uncolored node u∈VGu\in V_G and assigns a color ii to this node (breaking ties arbitrarily), updating the state to (G,c′)(G,c'), with c′(u)=ic'(u)=i and c′(v)=c(v) ∀v≠uc'(v)=c(v)\ \forall v\ne u.

Supposing that the color predictor can distinguish any rooted isomorphism, a single parameter setting can then express every kk-colorable graph of bounded size. At each extendable state, the predictor can memorize, for every uncolored node, the colors leading to an extendable successor. Since every uncolored node has at least one such color, selecting any node and any such color preserves extendability, so induction produces a proper coloring. (Thm. 5). While practical models generally cannot distinguish arbitrary rooted-graph isomorphism types [49], this shows that, at least in principle, sequential coloring has enough expressivity to represent valid coloring strategies.

Color symmetries

While the equivariance to permutations of the nodes is common in most graph tasks, graph coloring presents another symmetry: the color labels are arbitrary. Indeed, consistently permuting the color labels leaves the validity and the number of monochromatic edges of a coloring unchanged. Figure 2 shows two instances that are exactly the same up to a permutation of the partial colors, and illustrates that their solutions are also the same up to the same permutation. Formally, let a color permutation τ∈Sk\tau\in S_k act as (τ⋅c)(v)=τ(c(v))(\tau\cdot c)(v) = \tau(c(v)) if c(v)≠εc(v) \ne\varepsilon and (τ⋅c)(v)=ε(\tau\cdot c)(v) = \varepsilon otherwise. If c∗c^* is a valid solution for (G,c)(G,c), then for any τ∈Sk\tau\in S_k we have that τ⋅c∗\tau\cdot c^* is a valid solution for (G,τ⋅c)(G,\tau\cdot c).

Figure 2. Graph coloring is equivariant to color permutations. The instances (G,c)(G,c) and (G,c′)(G,c') differ only by exchanging blue and green, so the solutions c1∗c_1^* and c2∗c_2^* are related by the same permutation. Moreover, blue and yellow are unused in c′c' and thus interchangeable, so c2∗c_2^* and c3∗c_3^* are equivalent.

References

  1. [1]Reza Refaei Afshar, Yingqian Zhang, Murat Firat, and Uzay Kaymak. A state aggregation approach for solving knapsack problem with deep reinforcement learning. In Asian Conference on Machine Learning, pp. 81–96. PMLR, 2020.arxiv.org/abs/2004.12117
  2. [2]Abhinav Anand, Subrahmanya Swamy Peruru, and Amitangshu Pal. Vcolrl: Learn to solve the vertex coloring problem using reinforcement learning. Transactions on Machine Learning Research, 2025.
  3. [3]Kenneth Appel and Wolfgang Haken. Every planar map is four colorable. part i: Discharging. Illinois Journal of Mathematics, 21(3):429–490, 1977.DOI
  4. [4]Stefan Arnborg and Andrzej Proskurowski. Linear time algorithms for np-hard problems restricted to partial k-trees. Discrete applied mathematics, 23(1):11–24, 1989.DOI
  5. [5]Urvashi Arora, Prisha Jain, Ashutosh Rai, and Sandeep Kumar. Graph coloring via learning and metric-guided independent set extraction. Transactions on Machine Learning Research, 2026.
  6. [6]Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky. Graph isomorphism, color refinement, and compactness. computational complexity, 26(3):627–685, 2017.
  7. [7]Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.06450, 2016.arxiv.org/abs/1607.06450
  8. [8]László Babai, Paul Erdos, and Stanley M Selkow. Random graph isomorphism. SIAM Journal on computing, 9(3):628–635, 1980.DOI
  9. [9]Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In AAAI, 2020.arxiv.org/abs/1909.04063
  10. [10]Richard Beigel and David Eppstein. 3-coloring in time o (1.3289 n). Journal of Algorithms, 54(2):168–204, 2005.
  11. [11]Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940, 2016.arxiv.org/abs/1611.09940
  12. [12]Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d’horizon. European Journal of Operational Research, 290(2):405–421, 2021.arxiv.org/abs/1811.06128
  13. [13]Daniel Brélaz. New methods to color the vertices of a graph. Communications of the ACM, 22(4):251–256, 1979.DOI
  14. [14]Rowland Leonard Brooks. On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37(2):194–197, 1941.
  15. [15]Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Velicković. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24(130):1–61, 2023.
  16. [16]Michael W Carter, Gilbert Laporte, and Sau Yan Lee. Examination timetabling: Algorithmic strategies and applications. Journal of the operational research society, 47(3):373–383, 1996.
  17. [17]Gregory J Chaitin, Marc A Auslander, Ashok K Chandra, John Cocke, Martin E Hopkins, and Peter W Markstein. Register allocation via coloring. Computer languages, 6(1):47–57, 1981.DOI
  18. [18]James Crawford, Matthew Ginsberg, Eugene Luks, and Amitabha Roy. Symmetry-breaking predicates for search problems. KR, 96(1996):148–159, 1996.
  19. [19]Liam Davis, Leopold Haller, Alberto Alf arano, and Mark Santolucito. Lattice deduction transformers. arXiv preprint arXiv:2605.08605, 2026.arxiv.org/abs/2605.08605
  20. [20]Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Marc Andreoli. Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization. In NeurIPS, 2023.arxiv.org/abs/2301.03313
  21. [21]Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:1903.02428, 2019.arxiv.org/abs/1903.02428
  22. [22]Michael R Garey, David S Johnson, and Larry Stockmeyer. Some simplified np-complete problems. In ACM STOC, pp. 47–63, 1974.DOI
  23. [23]Lal George and Andrew W Appel. Iterated register coalescing. ACM Transactions on Programming Languages and Systems (TOPLAS), 18(3):300–324, 1996.
  24. [24]Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Orio Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, 2017.arxiv.org/abs/1704.01212
  25. [25]Ronald L Graham, Donald Ervin Knuth, and Oren Patashnik. Concrete mathematics: a foundation for computer science. Addison-Wesley Reading, MA, 1994.
  26. [26]Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https://www.gurobi.com.
  27. [27]Robert M. Haralick and Gordon L. Elliott. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14(3):263–313, 1980.
  28. [28]Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.arxiv.org/abs/1512.03385
  29. [29]Alain Hertz and Dominique de Werra. Using tabu search techniques for graph coloring. Computing, 39(4):345–351, 1987.DOI
  30. [30]Agnes M Herzberg and M Ram Murty. Sudoku squares and chromatic polynomials. Notices of the AMS, 54(6):708–717, 2007.
  31. [31]Marijn J Heule, Anthony Karahalios, and Willem-Jan van Hoeve. From cliques to colorings and back again. In International Conference on Principles and Practice of Constraint Programming, 2022.DOI
  32. [32]Jiayi Huang, Mostofa Patwary, and Gregory Diamos. Coloring big graphs with alphagozero. arXiv preprint arXiv:1902.10162, 2019.arxiv.org/abs/1902.10162
  33. [33]Alexia Jolicoeur-Martineau. Less is more: Recursive reasoning with tiny networks. arXiv preprint arXiv:2510.04871, 2025.
  34. [34]Nikolaos Karalias, Akbar Rafiey, Yifei Xu, Zhishang Luo, Behrooz Tahmasebi, Connie Jiang, and Stefanie Jegelka. Geometric algorithms for neural combinatorial optimization with constraints. In NeurIPS, 2025.
  35. [35]Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In NeurIPS, 2017.arxiv.org/abs/1704.01665
  36. [36]Minsu Kim, Junyoung Park, and Jink yoo Park. Sym-nco: Leveraging symmetry for neural combinatorial optimization. In NeurIPS, 2022.arxiv.org/abs/2205.13209
  37. [37]Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.arxiv.org/abs/1412.6980
  38. [38]Andreas Krebs and Oleg Verbitsky. Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth. In ACM/IEEE Symposium on Logic in Computer Science, 2015.
  39. [39]Thien Le, Tianyu Zhao, and Melanie Weber. Contrastive neural algorithmic reasoning for graph coloring. arXiv preprint arXiv:2606.03923, 2026.
  40. [41]Frank Thomson Leighton. A graph coloring algorithm for large scheduling problems. Journal of research of the national bureau of standards, 84(6):489, 1979.DOI
  41. [42]Henrique Lemos, Marcelo Prates, Pedro Avelar, and Luis Lamb. Graph colouring meets deep learning: Effective graph neural network models for combinatorial problems. In 2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI), pp. 879–885. IEEE, 2019.arxiv.org/abs/1903.04598
  42. [43]Wei Li, Ruxuan Li, Yuzhe Ma, Siu On Chan, David Pan, and Bei Yu. Rethinking graph neural networks for the graph coloring problem. arXiv preprint arXiv:2208.06975, 2022.
  43. [44]Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017.arxiv.org/abs/1711.05101
  44. [45]Yuankai Luo, Lei Shi, and Xiao-Ming Wu. Can classic gnns be strong baselines for graph-level tasks? simple architectures meet excellence. In ICML, 2025.
  45. [46]Enrico Malaguti and Paolo Toth. A survey on vertex coloring problems. International transactions in operational research, 17(1):1–34, 2010.DOI
  46. [47]Gary McGuire, Bastian Tugemann, and Gilles Civario. There is no 16-clue sudoku: Solving the sudoku minimum number of clues problem via hitting set enumeration. Experimental Mathematics, 23(2):190–217, 2014.DOI
  47. [48]Isabel Méndez-Díaz and Paula Zabala. A branch-and-cut algorithm for graph coloring. Discrete Applied Mathematics, 154(5):826–847, 2006.
  48. [49]Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 2019.arxiv.org/abs/1810.02244
  49. [50]Rasmus Palm, Ulrich Paquet, and Ole Winther. Recurrent relational networks. In NeurIPS, volume 31, 2018.arxiv.org/abs/1711.08028
  50. [51]Judea Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984.
  51. [52]Paolo Pellizzoni, Till Schulz, and Karsten Borgwardt. Gelato: Graph edit distance via autoregressive neural combinatorial optimization. In ICLR, 2026.
  52. [53]Jean-François Puget. An efficient way of breaking value symmetries. In AAAI, 2006.
  53. [54]Yeqing Qiu, Ye XUE, Akang Wang, Yiheng Wang, Qingjiang Shi, and Zhi-Quan Luo. ROS: A GNN-based relax-optimize-and-sample framework for max-$k$-cut problems. In ICML, 2025.arxiv.org/abs/2412.05146
  54. [56]Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas. The four-colour theorem. journal of combinatorial theory, Series B, 70(1):2–44, 1997.DOI
  55. [57]Joseph J Rotman. An introduction to the theory of groups. Springer Science & Business Media, 2012.
  56. [58]Ayesha Saeed, Ali Husnain, Anam Zahoor, and Rashad Mehmood Gondal. A comparative study of cat swarm algorithm for graph coloring problem: Convergence analysis and performance evaluation. International Journal of Innovative Research in Computer Science and Technology (IJIRCST), 12(4):1–9, 2024.DOI
  57. [59]Martin JA Schuetz, J Kyle Brubaker, Zhihui Zhu, and Helmut G Katzgraber. Graph coloring with physics-inspired graph neural networks. Physical Review Research, 4(4):043131, 2022.DOI
  58. [60]Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill. Learning a SAT solver from single-bit supervision. In ICLR, 2019.arxiv.org/abs/1802.03685
  59. [61]Robert E Tarjan and Mihalis Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on computing, 13(3):566–579, 1984.DOI
  60. [62]Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph neural networks for maximum constraint satisfaction. Frontiers in artificial intelligence, 3:580607, 2021.arxiv.org/abs/1909.08387
  61. [63]Jan Tönshoff, Berke Kisin, Jakob Lindner, and Martin Grohe. One model, any csp: graph neural networks as fast global search heuristics for constraint satisfaction. In IJCAI, 2023.
  62. [65]Michel Vasquez. New results on the queens_ n 2 graph coloring problem. Journal of Heuristics, 10(4):407–413, 2004.DOI
  63. [66]Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In NeurIPS, 2015.
  64. [67]Toby Walsh. Symmetry breaking constraints: Recent results. In AAAI, 2012.arxiv.org/abs/1204.3348
  65. [68]Guan Wang, Jin Li, Yuhao Sun, Xing Chen, Changling Liu, Yue Wu, Meng Lu, Sen Song, and Yasin Abbasi Yadkori. Hierarchical reasoning model. arXiv preprint arXiv:2506.21734, 2025.arxiv.org/abs/2506.21734
  66. [69]Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In ICML, 2019.arxiv.org/abs/1905.12149
  67. [70]George Watkins, Giovanni Montana, and Juergen Branke. Generating a graph colouring heuristic with deep q-learning and graph neural networks. In International conference on learning and intelligent optimization, pp. 491–505. Springer, 2023.arxiv.org/abs/2304.04051
  68. [71]Dominic JA Welsh and Martin B Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1):85–86, 1967.DOI
  69. [72]Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.arxiv.org/abs/1810.00826
  70. [73]Yudong Xu, Wenhao Li, Scott Sanner, and Elias Boutros Khalil. Self-supervised transformers as iterative solution improvers for constraint satisfaction. In ICML, 2025.arxiv.org/abs/2502.15794

Paper details

vlnc:W_3yzx3b67
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

generative AI tools

View statement
Looking for related papers…
Contents