One Color Preprocessing Improves DSATUR

# One Color Preprocessing Improves DSATUR
Source: [https://arxiv.org/html/2609.17633](https://arxiv.org/html/2609.17633)
## Abstract

The Graph Coloring Problem \(GCP\) is NP\-hard and DSATUR stands as one of the fastest heuristics for it despite producing colorings that typically use more colors than state\-of\-the\-art coloring algorithms\. We propose SSLD \(Semidefinite Spectral Learning with DSATUR\), which improves DSATUR by preprocessing a first good color class before letting DSATUR complete coloring the rest of the given graph\. We obtain this color class from a Semidefinite Programming \(SDP\), similar to an SDP used to compute the Lovász theta number\. To the best of our knowledge, SSLD is the first approach to improve DSATUR by preprocessing through fixed color classes\. We evaluate SSLD against DSATUR and against a naive 1\-color\-class preprocessing algorithm on DIMACS instances, random graphs \(Erdős–Rényi, Watts\-Strogatz, Barabási–Albert\), Frequency Assignment and Job Shop Scheduling instances\. SSLD matches or beats DSATUR in almost every case across over 1600 benchmark instances, and out performs the naive GISD baseline, allows us to confirm the value brought by the SDP\-guided choice of the first color class\. This quality comes at a runtime cost of roughly 195 times slower that DSATUR, but demonstrating that SDP\-guided preprocessing of a first color class is a direction for future improvements\.

## 1Introduction

The Graph Coloring Problem \(GCP\) is to color the vertices of a graph using as few colors as possible such that no adjacent vertices share the same color\. The GCP can also be considered as partitioning the vertex set of the graph into a minimum number of color groups such that no vertices in each color group are adjacent\. The GCP has numerous practical applications in various domains\[[1](https://arxiv.org/html/2609.17633#bib.bib35)\]and has been studied for a long time\. Graph coloring arises naturally in a variety of applications such as register allocation\[[2](https://arxiv.org/html/2609.17633#bib.bib44),[3](https://arxiv.org/html/2609.17633#bib.bib39),[4](https://arxiv.org/html/2609.17633#bib.bib38)\]and timetable or examination scheduling\[[5](https://arxiv.org/html/2609.17633#bib.bib42),[6](https://arxiv.org/html/2609.17633#bib.bib41)\]\. The minimum number of colors used in proper coloring is called the chromatic number of the graph and is denoted byχ⁡\(G\)\\chi\(G\)\. Determining the value ofχ⁡\(G\)\\chi\(G\)is NP\-hard\[[7](https://arxiv.org/html/2609.17633#bib.bib49)\]and even thekk\-Coloring problem is NP\-hard for everyk≥3k\\geq 3\.

Concerning exact algorithms, using dynamic programming an algorithm inO∗​\(2\.4423n\)O^\{\*\}\(2\.4423^\{n\}\)\[[8](https://arxiv.org/html/2609.17633#bib.bib36)\]has been derived\. Using the principle of inclusion–exclusion and Yates’s algorithm for the fast zeta transform, k\-colorability can be decided in timeO⁡\(2n​nO⁡\(1\)\)O\(2^\{n\}n^\{O\(1\)\}\)\[[9](https://arxiv.org/html/2609.17633#bib.bib25)\]for any k\. Faster algorithms are known for 3\- and 4\-colorability, which can be decided in timeO⁡\(1\.3289n\)O\(1\.3289^\{n\}\)\[[10](https://arxiv.org/html/2609.17633#bib.bib24)\]andO⁡\(1\.7272n\)O\(1\.7272^\{n\}\)\[[11](https://arxiv.org/html/2609.17633#bib.bib21)\]respectively\. In the case of perfect graphs, computing the chromatic number is polynomial\[[12](https://arxiv.org/html/2609.17633#bib.bib34)\]\.

Nevertheless, exact algorithms are only tractable up to 300 vertices \(taking 10 minutes for a random graph\), that is why we need approximation algorithms or heuristics for bigger graphs\. Unfortunately, it has been shown that if certain reasonable complexity conjectures hold thenkk\-Coloring is hard to approximate withinn1−ϵn^\{1\-\\epsilon\}for anyϵ\>0\\epsilon\>0\[[13](https://arxiv.org/html/2609.17633#bib.bib22)\]\. Furthermore, for any constantγ\>0\\gamma\>0, there is no polynomial time algorithm that approximates the chromatic number within factorn/2\(log⁡\(n\)\)3/4\+γn/2^\{\(\\log\(n\)\)^\{3/4\+\\gamma\}\}wherennis the size of the graph assuming another reasonable complexity conjecture\[[14](https://arxiv.org/html/2609.17633#bib.bib23)\]\.

### 1\.1Approximation algorithms

The first approximation algorithm shows that a version of the greedy algorithm gives anO⁡\(n/log⁡n\)O\(n/\\log n\)\-approximation algorithm forkk\-coloring\[[15](https://arxiv.org/html/2609.17633#bib.bib45)\]\.

Later,\[[16](https://arxiv.org/html/2609.17633#bib.bib48)\]introduced an approach to approximate graph coloring via semidefinite programming\. Their algorithm solves an Semidefinite Programming \(SDP\) relaxation linked to the Lovász theta number to obtain a vector representation of the graph, then extracts a coloring after multiple iterations of applying a random hyperplane rounding\. For a 3\-colorable graph onnnvertices, their algorithm produces a coloring usingO⁡\(n0\.387\)O\(n^\{0\.387\}\)colors, and for akk\-colorable graph, it produces a coloring usingO⁡\(n1−3/\(k\+1\)\)O\(n^\{1\-3/\(k\+1\)\}\)colors\. Given that these theoretical guarantees are weaker than theχ\\chi, their algorithm establishes the key connection between SDP relaxations and coloring extraction via randomized rounding that other algorithms, including the one presented in this work, build on\.

### 1\.2Heuristics

Many heuristics have been proposed for graph coloring; we summarize them by family\.

The earliest ones are greedy: the vertices are colored one after another, each vertex receiving a color that none of its already colored neighbours uses\. The methods of this family differ in the order in which the vertices are considered and in the way the color is chosen; DSATUR\[[17](https://arxiv.org/html/2609.17633#bib.bib46)\]and RLF\[[18](https://arxiv.org/html/2609.17633#bib.bib17)\]are the two best known\. They are fast, but the colorings they return use more colors than the best known ones, so they are now used mainly to produce initial solutions for other algorithms\.

A second family is local search: a single coloring is modified repeatedly, by small or large steps\. Some methods keep the coloring proper at every step, others allow improper colorings and aim at reducing the number of monochromatic edges\.\[[19](https://arxiv.org/html/2609.17633#bib.bib29),[20](https://arxiv.org/html/2609.17633#bib.bib33),[21](https://arxiv.org/html/2609.17633#bib.bib9),[22](https://arxiv.org/html/2609.17633#bib.bib2),[23](https://arxiv.org/html/2609.17633#bib.bib3),[24](https://arxiv.org/html/2609.17633#bib.bib6),[25](https://arxiv.org/html/2609.17633#bib.bib47),[26](https://arxiv.org/html/2609.17633#bib.bib7),[27](https://arxiv.org/html/2609.17633#bib.bib10),[28](https://arxiv.org/html/2609.17633#bib.bib26),[29](https://arxiv.org/html/2609.17633#bib.bib27),[30](https://arxiv.org/html/2609.17633#bib.bib8),[31](https://arxiv.org/html/2609.17633#bib.bib32),[32](https://arxiv.org/html/2609.17633#bib.bib11)\]

A third family is evolutionary algorithms: a population of colorings evolves under modifications that are borrowed from local search:\[[33](https://arxiv.org/html/2609.17633#bib.bib4),[34](https://arxiv.org/html/2609.17633#bib.bib13),[35](https://arxiv.org/html/2609.17633#bib.bib5),[36](https://arxiv.org/html/2609.17633#bib.bib14),[37](https://arxiv.org/html/2609.17633#bib.bib15),[38](https://arxiv.org/html/2609.17633#bib.bib16),[39](https://arxiv.org/html/2609.17633#bib.bib1)\]\.

A few methods combine several of these families\[[40](https://arxiv.org/html/2609.17633#bib.bib31),[41](https://arxiv.org/html/2609.17633#bib.bib12)\]\. Finally, a heuristic derived from a branch\-and\-bound algorithm has also been proposed\[[42](https://arxiv.org/html/2609.17633#bib.bib30)\]\.

### 1\.3The Lovászϑ\\varthetaFunction

Before defining the Lovászϑ\\varthetafunction\[[43](https://arxiv.org/html/2609.17633#bib.bib37)\], we recall some notation\. Given a graphGG, we writeω⁡\(G\)\\omega\(G\)for its clique number,χ⁡\(G\)\\chi\(G\)for its chromatic number andG¯\\overline\{G\}for its complement\.

##### Definition\.

An orthonormal representation of a graphG=\(V,E\)G=\(V,E\)with vertex setV=\{1,…,n\}V=\\\{1,\\dots,n\\\}is a set of unit vectors\(u1,…,un\)\(u\_\{1\},\\dots,u\_\{n\}\)inℝn\\mathbb\{R\}^\{n\}such thatuiT​uj=0​if​i≠j​and​\{i,j\}∉Eu\_\{i\}^\{T\}u\_\{j\}=0\\text\{ if \}i\\neq j\\text\{ and \}\\\{i,j\\\}\\notin E\.

##### Definition \(Lovászϑ\\varthetafunction\)\.

LetGGbe a graph onnnvertices\. The Lovászϑ\\varthetafunction ofGGis:

ϑ⁡\(G\)=minc,U⁡max1≤i≤n​1\(cT​ui\)2\\vartheta\(G\)=\\min\_\{c,U\}\\max\_\{1\\leq i\\leq n\}\\frac\{1\}\{\(c^\{T\}u\_\{i\}\)^\{2\}\}where the minimum is taken over all unit vectorsccofℝn\\mathbb\{R\}^\{n\}and over allU=\{u1,…,un\}U=\\\{u\_\{1\},\\dots,u\_\{n\}\\\}orthonormal representations ofGG\.

The Lovászϑ\\varthetafunction is upper bounded by the chromatic number of the complement graph:

##### Theorem\[[43](https://arxiv.org/html/2609.17633#bib.bib37)\]\.

ω⁡\(G\)≤ϑ⁡\(G¯\)≤χ⁡\(G\)\\omega\(G\)\\leq\\vartheta\(\\overline\{G\}\)\\leq\\chi\(G\)\.

### 1\.4Semidefinite Programming Formulation

We writeSnS^\{n\}for the space of real symmetricn×nn\\times nmatrices,\(A,B\)=tr⁡\(A​B\)\(A,B\)=\\operatorname\{tr\}\(AB\)for the trace inner product onSnS^\{n\}, andA⪰0A\\succeq 0to say thatA∈SnA\\in S^\{n\}is positive semidefinite\.

A semidefinite program consists in optimizing a linear function over the intersection of the cone of positive semidefinite matrices with an affine subspace\. It contains linear programming as the particular case where all the matrices involved are diagonal\. SDP can be solved in polynomial time to arbitrary precision\[[44](https://arxiv.org/html/2609.17633#bib.bib43)\]\.

The Lovászϑ\\varthetafunctionϑ⁡\(G\)\\vartheta\(G\)can be computed thanks to the following SDP formulation, which we call the L\-SDP ofGG:

maximizeXn\+2,n\+2\\displaystyle X\_\{n\+2,n\+2\}whereX⪰0​and​X∈Sn\+2​\(ℝ\)\\displaystyle X\\succeq 0\\text\{ and \}X\\in S^\{n\+2\}\(\\mathbb\{R\}\)subject toXi,i=1,∀1≤i≤n\+1\\displaystyle X\_\{i,i\}=1,\\quad\\forall\\,1\\leq i\\leq n\+1Xi,j=0​if​\{i,j\}∉E\\displaystyle X\_\{i,j\}=0\\text\{ if \}\\\{i,j\\\}\\notin EXn\+1,j≥Xn\+2,n\+2,∀1≤j≤n\\displaystyle X\_\{n\+1,j\}\\geq X\_\{n\+2,n\+2\},\\quad\\forall\\,1\\leq j\\leq nXn\+2,j=0,∀1≤j≤n\+1\.\\displaystyle X\_\{n\+2,j\}=0,\\quad\\forall\\,1\\leq j\\leq n\+1\.
According to\[[43](https://arxiv.org/html/2609.17633#bib.bib37)\], by callingttthe optimal valueXn\+2,n\+2X\_\{n\+2,n\+2\}, then we haveϑ⁡\(G\)=1/t\\vartheta\(G\)=1/\\sqrt\{t\}\. Thusϑ⁡\(G\)\\vartheta\(G\)can be computed in polynomial time\. Note that the orthonormal representation corresponding to this optimal value can be derived from the Gram representation ofX∗X^\{\*\}\.

### 1\.5Our Contribution

We focus on the greedy algorithm DSATUR which is one of the fastest heuristics\. The goal is to improve the number of colors returned by this algorithm by starting with a good independent set \(a color class\) and complementing the color class with the DSATUR algorithm\. Our SSLD algorithm will try different independent sets and return the best result\.

To find appropriate independent sets, our algorithm will make use of a Semidefinite Programming \(SDP\) relaxation with a spectral decomposition and randomized rounding procedure\. We propose a new SDP similar to the one used in the Lovász Theta function which is a parameter lower bound on the chromatic number\.

We conduct an experimental assessment on benchmarks from the DIMACS competition, randomly generated graphs, frequency assignment problems, and job shop scheduling instances\. We show that SSLD consistently uses fewer colors than DSATUR on these instances\.

To the best of our knowledge, our algorithm is the first which tries to improve the DSATUR by preprocessing by fixing some color classes\.

## 2DSATUR preprocessing

Given any algorithm𝒜\\mathcal\{A\}that returns an independent setIIofGG, the preprocessing strategy assigns color00to all vertices inIIand completes the coloring of the remaining vertices with DSATUR \(Algorithm[1](https://arxiv.org/html/2609.17633#algorithm1)\)\. The number of colors used in the final coloring depends on the size ofIIand on which vertices it contains because a poorly chosen independent set, even a large one, can leave a harder subgraph for DSATUR and result in more colors than plain DSATUR\.

Algorithm 1DSATUR CompletionFunction*DSaturCompletion\(*G⁡\(V,E\)G\(V,E\),c:V′→ℕc:V^\{\\prime\}\\to\\mathbb\{N\}\(partial coloring\)*\)*:

U←V∖V′U\\leftarrow V\\setminus V^\{\\prime\};

while*U≠∅U\\neq\\emptyset*do

v←arg​maxu∈U⁡\(\|sat⁡\(u\)\|,deg⁡\(u\)\)v\\leftarrow\\displaystyle\\argmax\_\{u\\in U\}\(\|\\sat\(u\)\|,\\deg\(u\)\);

c⁡\(v\)←min⁡\{k∈ℕ:k∉c⁡\(N⁡\(v\)\)\}c\(v\)\\leftarrow\\min\\\{k\\in\\mathbb\{N\}:k\\notin c\(N\(v\)\)\\\};

U←U∖\{v\}U\\leftarrow U\\setminus\\\{v\\\};

return*cc*

## 3Naive DSATUR preprocessing

We initially tried the most naive possible variant of our idea: preprocess DSATUR by fixing one color class taken as a maximal independent set built with a greedy algorithm, and completing the rest with DSATUR as before\. This algorithm is described in Algorithm[2](https://arxiv.org/html/2609.17633#algorithm2)and we call it Greedy Independent Set with DSATUR \(GISD\)\.

Since it requires no SDP solve, its overhead over plain DSATUR is negligible, as reflected by its near\-zerot⁡\(s\)t\(s\)column throughout \(Section[5](https://arxiv.org/html/2609.17633#S5)\)\.

Algorithm 2GISwDSATURFunction*GISD\(*G⁡\(V,E\)G\(V,E\)*\)*:

I←∅I\\leftarrow\\emptyset;

for*v∈Vv\\in V*do

if*vvhas no neighbor inII*then

I←I∪\{v\}I\\leftarrow I\\cup\\\{v\\\};

c←\{v:0∣v∈I\}c\\leftarrow\\\{v:0\\mid v\\in I\\\};

c←c\\leftarrowDSaturCompletion\(*G,cG,c*\);

return*\|colors⁡\(c\)\|\|\\colors\(c\)\|*

## 4SSLD Description

### 4\.1The D\-SDP

We defineJ∈ℝn×nJ\\in\\mathbb\{R\}^\{n\\times n\}as the all\-ones matrix\. The SDP solved by SSLD is:

maximizeX\\displaystyle\\operatorname\*\{maximize\}\_\{X\}\\quadtr⁡\(X​J\)\\displaystyle\\tr\(XJ\)subject toX⪰0\\displaystyle X\\succeq 0Xi​i=1∀i∈V\\displaystyle X\_\{ii\}=1\\quad\\forall i\\in VXi​j=0∀i​j∈E\\displaystyle X\_\{ij\}=0\\quad\\forall ij\\in EThis problem computes an orthonormal representation ofG¯\\overline\{G\}and is related to the SDP used by Lovász to computeϑ⁡\(G\)\\vartheta\(G\), but differs in its objective and carries no proven theoretical guarantees\.

Orthogonal representations will be used as follows to detect color classes\. If we consider a unit vector called, a centroid, and if we compute the scalar products of the vertices with this centroid, then all the vertices which have a high scalar products are not adjacent \(because adjacent vertices are orthogonal and thus cannot be in a small cap\)\. Therefore we will try to find good centroids for detecting color classes\. This algorithm is described in Algorithm[3](https://arxiv.org/html/2609.17633#algorithm3)\.

Algorithm[3](https://arxiv.org/html/2609.17633#algorithm3)generalizes GISD \(Algorithm[2](https://arxiv.org/html/2609.17633#algorithm2)\): GISD is the special case obtained by replacing the spectral scoreppwith the identity ordering onVV\. As we previously said, since it requires no SDP solve, its overhead over plain DSATUR is negligible\. However, as we show in Section[5](https://arxiv.org/html/2609.17633#S5), the naive preprocessing is inconsistent: it sometimes matches or slightly improves on DSATUR, but on several instances \(e\.g\.DSJC125\.9,queen11\_11\) it performs strictly worse, since an arbitrarily\-ordered independent set is not guaranteed to be a good first color class\. SSLD addresses this by replacing the identity ordering with one derived from the SDP relaxation\.

Algorithm 3Projection\-Greedy Independent SetFunction*ProjGreedyIS\(*G⁡\(V,E\)G\(V,E\),S⊆VS\\subseteq V,p∈ℝnp\\in\\mathbb\{R\}^\{n\}*\)*:

I←∅I\\leftarrow\\emptyset;

for*v∈Sv\\in Ssorted by decreasingpvp\_\{v\}*do

if*vvhas no neighbor inII*then

I←I∪\{v\}I\\leftarrow I\\cup\\\{v\\\};

return*II*

The Lovász SDP is also finding an orthogonal representation ofGGbut it looks for one maximizing the minimum of the scalar products with a unit vector \(called the handle\)\. Thus this optimal orthogonal representation keeps the vertices in the smallest cap\. Thus the color classes centroids will get more vertices because the vertices are in a small cap\. And thus there may not be many color classes\.

The objective of the D\-SDP is

tr⁡\(X​J\)=∑i∈VXi​i\+∑i​j∈E\(Xi​j\+Xj​i\)\+∑i<j,i​j∉E2​Xi​j=n\+2​∑i<j,i​j∉E⟨vi,vj⟩\\tr\(XJ\)=\\sum\_\{i\\in V\}X\_\{ii\}\+\\sum\_\{ij\\in E\}\(X\_\{ij\}\+X\_\{ji\}\)\+\\sum\_\{i<j,\\,ij\\notin E\}2X\_\{ij\}=n\+2\\sum\_\{i<j,\\,ij\\notin E\}\\langle v\_\{i\},v\_\{j\}\\ranglewhere theviv\_\{i\}is the vector representing the vertexii\. So the D\-SDP directly rewards aligning vertices that could form a common independent set\. Therefore the D\-SDP may reward big independent sets\.

Nevertheless, the Lovász SDP is slower to compute and gives no better results according to Table[1](https://arxiv.org/html/2609.17633#S5.T1)\.

### 4\.2Algorithm Description

SSLD solves the D\-SDP to obtain a matrixX∗X^\{\*\}, whose eigendecompositionX∗=Q​Λ​Q⊤X^\{\*\}=Q\\Lambda Q^\{\\top\}results in a spectral embedding where each vertexiiis represented as a vectorVi∈ℝnV\_\{i\}\\in\\mathbb\{R\}^\{n\}on the unit sphere\. At each ofTTiterations, SSLD draws a random directionrraccording to𝒩⁡\(0,I\)\\mathcal\{N\}\(0,I\)and projects all vertex embeddings onto it, producing scalar scoresp=V​rp=Vr\. A greedy independent set is then extracted from the full vertex set by processing vertices in decreasing order ofpvp\_\{v\}\. This independent set is assigned color 0, and the remaining uncolored subgraph is completed with the DSATUR heuristic\. The coloring achieving the fewest colors across allTTattempts is returned\.

Algorithm 4Semidefinite Spectral Learning with DSATURFunction*SSLD\(*a graphGG*\)*:

X∗←SDP⁡\(G\)X^\{\*\}\\leftarrow\\mathrm\{SDP\}\(G\);

\(Λ,Q\)←\(\\Lambda,Q\)\\leftarroweigendecomposition of

X∗X^\{\*\};

V←Q⋅diag⁡\(max⁡\(Λ,0\)\)V\\leftarrow Q\\cdot\\mathrm\{diag\}\(\\sqrt\{\\max\(\\Lambda,0\)\}\);

k∗←\+∞k^\{\*\}\\leftarrow\+\\infty;

for*i=1i=1toTT*do

r←𝒩⁡\(0,I\)r\\leftarrow\\mathcal\{N\}\(0,I\);

p←V​rp\\leftarrow Vr;

I←I\\leftarrowProjGreedyIS\(*G,V,pG,V,p*\);

c←c\\leftarrowDSaturCompletion\(*G,\{v:0∣v∈I\}G,\\\{v:0\\mid v\\in I\\\}*\);

if*\|colors⁡\(c\)\|<k∗\|\\colors\(c\)\|<k^\{\*\}*then

k∗←\|colors⁡\(c\)\|k^\{\*\}\\leftarrow\|\\colors\(c\)\|;

return*k∗k^\{\*\}*

#### Parameter Selection

The number of attemptsTTcontrols the trade\-off between solution quality and runtime\. To quantify this trade\-off, we generate Erdős–Rényi graphsG⁡\(n,0\.2\)G\(n,0\.2\)forn∈\{100,200,300,400,500\}n\\in\\\{100,200,300,400,500\\\}and, for each graph, run SSLD over 10 independent random seeds, recording the best chromatic number found so far at each attempt count up toT=1000T=1000\. Figure[1](https://arxiv.org/html/2609.17633#S4.F1)reports the mean of these best\-so\-far values as a function ofTT, together with the chromatic number obtained by plain DSATUR \(without SDP preprocessing\) as a horizontal reference for eachnn\. An “x” marks the first attempt at which SSLD strictly improves on the DSATUR baseline, and a “o” marks an instance where SSLD ties but does not surpass it\. Across all tested sizes, the bulk of the improvement is obtained within the first few dozen attempts, after which the curves plateau, suggesting thatTTcan be fixed to a modest value without a significant loss in solution quality\.

Figure 1:SSLD convergence vs\. number of attempts\.We fixT=500T=500as the default number of attempts, a choice supported across both the sparse regime \(p=0\.2p=0\.2,n≤500n\\leq 500, Figure[1](https://arxiv.org/html/2609.17633#S4.F1)\) and denser instances \(p∈\{0\.2,0\.4,0\.6\}p\\in\\\{0\.2,0\.4,0\.6\\\},n∈\{100,…,500\}n\\in\\\{100,\\dots,500\\\}\): in every configuration tested, the mean best \(so far\) chromatic number atT=500T=500differs from that atT=1000T=1000by at most0\.20\.2\. Therefore, doubling the attempt budget beyond500500would yield no meaningful gain in coloring quality regardless of density, since each attempt adds a fixed cost \(a random projection, greedy independent set extraction, and DSATUR completion\) beyond the single SDP solve per graph,T=500T=500captures nearly all of the achievable improvement over DSATUR\.

Note that we can also run SSLD without a fixed T\. It would be a time\-budget variant of the algorithm that would run until a given time limit is reached, making it more flexible\.

## 5Experimentation

### 5\.1Benchmark Instances

We evaluate SSLD on different categories of instances\. The DIMACS challenge\[[45](https://arxiv.org/html/2609.17633#bib.bib28)\]provides the standard hard instances used to compare graph coloring algorithms in the literature\. We complement these with three families of synthetic random graphs: Erdős–Rényi\[[46](https://arxiv.org/html/2609.17633#bib.bib18)\], Watts\-Strogatz\[[47](https://arxiv.org/html/2609.17633#bib.bib19)\], and Barabási–Albert\[[48](https://arxiv.org/html/2609.17633#bib.bib20)\]\. We further evaluate on real\-world instances derived from two applications: frequency assignment problems and job shop scheduling\. Finally, we evaluate on the adversarial family of graphs of Spinrad and Vijayan\[[49](https://arxiv.org/html/2609.17633#bib.bib40)\], for which DSATUR provably requiresnncolors on a 3\-colorable graph, providing a worst\-case stress test for any DSATUR\-based method\.

#### Hard\-to\-Color Instances for DSATUR

We usually evaluate the performance of greedy coloring heuristics through their worst\-case asymptotic guarantees\. Spinrad and Vijayan\[[49](https://arxiv.org/html/2609.17633#bib.bib40)\]demonstrated that the DSATUR algorithm admits an adversarial familyGnG\_\{n\}of 3\-colorable graphs on3​n−43n\-4vertices for which DSATUR may usenncolors\.

For anyn∈ℕ≥3n\\in\\mathbb\{N\}\_\{\\geq 3\},Gn=\(Vn,En\)G\_\{n\}=\(V\_\{n\},E\_\{n\}\)whereVn=Wn∪Wn′∪Wn′′V\_\{n\}=W\_\{n\}\\cup W^\{\\prime\}\_\{n\}\\cup W^\{\\prime\\prime\}\_\{n\}andEn=En1∪En2∪En3E\_\{n\}=E^\{1\}\_\{n\}\\cup E^\{2\}\_\{n\}\\cup E^\{3\}\_\{n\}, withWn=\{v1,…,vn−2\}W\_\{n\}=\\\{v\_\{1\},\\dots,v\_\{n\-2\}\\\},Wn′=\{v1′,…,vn−1′\}W^\{\\prime\}\_\{n\}=\\\{v^\{\\prime\}\_\{1\},\\dots,v^\{\\prime\}\_\{n\-1\}\\\},Wn′′=\{v2′′,…,vn′′\}W^\{\\prime\\prime\}\_\{n\}=\\\{v^\{\\prime\\prime\}\_\{2\},\\dots,v^\{\\prime\\prime\}\_\{n\}\\\}, and edge setsEn1=\{\(vi′,vi\+1′′\):0<i<n\}E^\{1\}\_\{n\}=\\\{\(v^\{\\prime\}\_\{i\},v^\{\\prime\\prime\}\_\{i\+1\}\):0<i<n\\\},En2=\{\(vi,vj′\):i≠j\}E^\{2\}\_\{n\}=\\\{\(v\_\{i\},v^\{\\prime\}\_\{j\}\):i\\neq j\\\},En3=\{\(vi,vj′′\):i<j\}E^\{3\}\_\{n\}=\\\{\(v\_\{i\},v^\{\\prime\\prime\}\_\{j\}\):i<j\\\}\.

Figure 2:The graphG5G\_\{5\}for which DSATUR use55colors despiteχ⁡\(G5\)=3\\chi\(G\_\{5\}\)=3\.Since there are no edges between vertices within the same partition,GnG\_\{n\}is 3\-colorable, withWnW\_\{n\},Wn′W^\{\\prime\}\_\{n\}, andWn′′W^\{\\prime\\prime\}\_\{n\}forming the three independent color classes \(Figure[2](https://arxiv.org/html/2609.17633#S5.F2)\)\. Spinrad and Vijayan show that the adversarial coloring sequencesns\_\{n\}causes DSATUR to assign a distinct color to each ofviv\_\{i\},vi′v^\{\\prime\}\_\{i\}, andvi′′v^\{\\prime\\prime\}\_\{i\}, resulting innncolors on a graph with chromatic number 3\. This family thus provides a worst\-case benchmark against which the improvement brought by SSLD can be measured\.

#### DIMACS Instances

The DIMACS implementation challenge\[[45](https://arxiv.org/html/2609.17633#bib.bib28)\]established a standard set of benchmark instances for the graph coloring problem, now widely used to evaluate and compare coloring algorithms in the literature\. The benchmark contains instances from several structured families, each with distinct combinatorial properties that stress different aspects of coloring algorithms\.

TheDSJCfamily consists of random graphsG⁡\(n,p\)G\(n,p\)generated with the DSJC generator, parameterized by densityp∈\{0\.1,0\.5,0\.9\}p\\in\\\{0\.1,0\.5,0\.9\\\}and sizen∈\{125,250,500,1000\}n\\in\\\{125,250,500,1000\\\}\. Theflatfamily contains equitablykk\-colorable random graphs, designed so that the chromatic number is known exactly\. Thequeenfamily derives from then×nn\\times nqueens problem on a chessboard where vertices represent squares and edges connect squares that share a row, column, or diagonal\. Themycielfamily consists of Mycielski graphsMkM\_\{k\}, which are triangle\-free graphs with arbitrarily large chromatic number, constructed recursively so thatχ⁡\(Mk\)=k\\chi\(M\_\{k\}\)=kwhileω⁡\(Mk\)=2\\omega\(M\_\{k\}\)=2\. Themilesfamily encodes geometric distance graphs on US cities\. Finally, the register allocation family provides conflict graphs derived from compiler register allocation problems\.

We evaluate over these families covering sparse, dense, structured, and random instances, following a subset of the selection in\[[37](https://arxiv.org/html/2609.17633#bib.bib15)\]\.

#### Scheduling Instances

The job shop scheduling problem consists of assigning a set of jobs to machines over a set of time slots subject to precedence and resource constraints\. A classical reduction to graph coloring\[[6](https://arxiv.org/html/2609.17633#bib.bib41)\]assigns a vertex to each job and introduces an edge between two jobs that cannot be executed simultaneously due to shared resource requirements\. A properkk\-coloring of the resulting conflict graph yields a feasible schedule usingkktime slots, and the chromatic numberχ⁡\(G\)\\chi\(G\)equals the minimum number of time slots required\. We evaluate on instances from the COLOR benchmark\[[45](https://arxiv.org/html/2609.17633#bib.bib28)\], which provide conflict graphs derived from real industrial job shop scheduling problems\.

#### Frequency Assignment Problems \(FAP\)

The frequency assignment problem \(FAP\) arises in the planning of radio communication networks, where a set of transmitters must be assigned operating frequencies such that co\-channel interference between geographically proximate transmitters is avoided\.

Formally, given a set of transmittersTTand an interference relationI⊆\(T2\)I\\subseteq\\binom\{T\}\{2\}consisting of the unordered pairs of transmitters that mutually interfere, the problem requires finding an assignmentf:T→ℕf:T\\to\\mathbb\{N\}such thatf⁡\(ti\)≠f⁡\(tj\)f\(t\_\{i\}\)\\neq f\(t\_\{j\}\)for all\{ti,tj\}∈I\\\{t\_\{i\},t\_\{j\}\\\}\\in I, while minimizing\|f⁡\(T\)\|\|f\(T\)\|\. This is equivalent to the chromatic number of the interference graphG=\(T,I\)G=\(T,I\)\.

We use the CELAR and GRAPH instance families from the Radio Link Frequency Assignment Problem benchmark\[[23](https://arxiv.org/html/2609.17633#bib.bib3)\], derived from French military communication network planning data and widely adopted as standard benchmarks in the graph coloring literature\[[37](https://arxiv.org/html/2609.17633#bib.bib15),[40](https://arxiv.org/html/2609.17633#bib.bib31)\]\.

#### Random Graphs

For random graphs, we have chosen these three most common models:

- •Erdős–Rényi model\[[46](https://arxiv.org/html/2609.17633#bib.bib18)\]\(also known asG⁡\(n,p\)G\(n,p\)\): given parametersn∈ℕn\\in\\mathbb\{N\}andp∈\[0,1\]p\\in\[0,1\], creates a graph withnnvertices such that each edge appears independently with probabilitypp\.
- •Watts\-Strogatz model\[[47](https://arxiv.org/html/2609.17633#bib.bib19)\]: given parametersn∈ℕn\\in\\mathbb\{N\},k∈ℕk\\in\\mathbb\{N\}andβ∈\[0,1\]\\beta\\in\[0,1\], this algorithm creates a graph withnnvertices by rewiring a ring lattice, producing graphs whose structural properties resemble those found in real\-world networks\.
- •Barabási–Albert model\[[48](https://arxiv.org/html/2609.17633#bib.bib20)\]: given parametersn∈ℕn\\in\\mathbb\{N\}andm∈ℕm\\in\\mathbb\{N\}, this algorithm grows a graph tonnvertices by adding one vertex at a time, each new vertex connecting tommexisting vertices chosen with probability proportional to their current degree, a preferential attachment mechanism where already well\-connected vertices tend to attract even more connections\.

### 5\.2Results

We use the implementation of DSATUR from networkx Python package\. Experiments are conducted under the following settings:

OSWindows 11 Pro 22H2 \(build 22621\.382\)CPUIntel Core i7\-14700K @ 5\.60 GHzRAM16 GB DDR5 6000 MHz CL40LanguagePython 3\.13\.5LibrariesNumPy, SciPy, NetworkX, CVXPYSDP solverSCS \(via CVXPY, toleranceϵ=10−6\\epsilon=10^\{\-6\}\)
Each SSLD result is reported over 5 independent runs with different random seeds\. The hit column indicates how many of those 5 runs achieved the reported number of colors k, giving a sense of the algorithm\.

#### Lovász vs\. D\-SDP: preliminary comparison

SSLD \[D\-SDP\]SSLD \[L\-SDP\]Instance\|V\|\|V\|\|E\|\|E\|kkhitt⁡\(s\)t\(s\)kkhitt⁡\(s\)t\(s\)DSJCDSJC125\.112573665/51\.57665/53\.751DSJC125\.51253891191/51\.728191/57\.588DSJC125\.91256961484/52\.503485/54\.976DSJC250\.1250321895/57\.61994/521\.1DSJC250\.525015668341/57\.453355/538\.3RR125\.112520955/53\.67255/53\.482R125\.1c1257501465/511\.0465/52\.746R125\.51253838375/514\.3375/5126\.8R250\.125086785/538\.685/5104\.0flatflat300\_20\_030021375395/511\.0395/5101\.7flat300\_26\_030021633391/511\.3391/560\.5flat300\_28\_030021695394/511\.0395/569\.5Table 1:
#### Hard\-to\-Color Instances benchmark

DSATURGISDSSLDInstance\|V\|\|V\|χ\\chikkt⁡\(s\)t\(s\)kkt⁡\(s\)t\(s\)kkt⁡\(s\)t\(s\)\(hit\)G5G\_\{5\}31350\.00030\.0003\(5/5\)0\.077G10G\_\{10\}663100\.00230\.0003\(5/5\)0\.339G20G\_\{20\}1363200\.01130\.0013\(5/5\)2\.173G50G\_\{50\}3463500\.12630\.0013\(5/5\)20\.5G100G\_\{100\}69631000\.95230\.0053\(5/5\)102\.9Table 2:
#### DIMACS benchmark

Table 3:DIMACS benchmark results\.DSATURGISDSSLDInstance\|V\|\|V\|\|E\|\|E\|kkt⁡\(s\)t\(s\)kkt⁡\(s\)t\(s\)kk\(hit\)t⁡\(s\)t\(s\)DSJCDSJC125\.112573660\.00760\.0016\(5/5\)1\.576DSJC125\.51253891220\.016220\.00219\(1/5\)1\.728DSJC125\.91256961510\.025530\.00248\(4/5\)2\.503DSJC250\.12503218100\.036100\.0039\(5/5\)7\.619DSJC250\.525015668370\.104370\.00734\(1/5\)7\.453DSJC250\.925027897920\.165890\.00885\(3/5\)12\.4DSJC500\.150012458160\.232160\.01415\(5/5\)30\.9DSJC500\.550062624650\.816650\.02662\(2/5\)37\.1DSJC500\.95001124371701\.3841650\.031159\(1/5\)80\.1DSJC1000\.1100049629271\.709260\.05625\(5/5\)131\.0DSJC1000\.510002498261157\.3281130\.098112\(5/5\)128\.1DSJC1000\.9100044944929912\.5743050\.131292\(2/5\)258\.3DSJRDSJR500\.15003555130\.108140\.010T/O \(–\)3600DSJR500\.1c500121275901\.558900\.032T/O \(–\)3600RR125\.112520950\.00550\.0005\(5/5\)3\.672R125\.1c1257501460\.025460\.00246\(5/5\)11\.0R125\.51253838380\.017380\.00237\(5/5\)14\.3R250\.125086780\.02280\.0028\(5/5\)38\.6R250\.1c25030227650\.187650\.00864\(5/5\)210\.3R250\.525014849680\.109680\.00666\(2/5\)290\.9RgR50\_1g5010840\.00140\.0003\(5/5\)0\.166R50\_5g50612110\.002110\.00010\(5/5\)0\.217R50\_9g501092220\.002220\.00021\(5/5\)0\.439R75\_1g7025150\.00250\.0004\(5/5\)0\.328R75\_5g751407150\.004160\.00114\(5/5\)0\.457R75\_9g752513360\.006350\.00134\(5/5\)0\.816R100\_1g10050960\.00460\.0005\(5/5\)0\.809R100\_5g1002456180\.008170\.00117\(5/5\)0\.934R100\_9g1004438410\.012410\.00138\(5/5\)1\.339flatflat300\_20\_030021375420\.178400\.00839\(5/5\)11\.0flat300\_26\_030021633410\.168430\.00839\(1/5\)11\.3flat300\_28\_030021695420\.167420\.00839\(4/5\)11\.0flat1000\_50\_010002450001146\.8701150\.097111\(4/5\)119\.9flat1000\_60\_010002458301146\.9191140\.100110\(1/5\)118\.7flat1000\_76\_010002467081157\.2091150\.100111\(1/5\)128\.0queenqueen5\_52516050\.00050\.0005\(5/5\)0\.086queen6\_63629090\.00190\.0008\(5/5\)0\.220queen7\_749476110\.001100\.0009\(5/5\)0\.587queen8\_864728120\.002110\.00010\(5/5\)0\.541queen8\_12961368140\.006150\.00112\(1/5\)0\.857queen9\_9811056130\.004140\.00111\(5/5\)0\.987queen10\_101001470140\.006130\.00112\(1/5\)1\.394queen11\_111211980150\.009170\.00114\(5/5\)2\.491queen12\_121442596160\.014160\.00215\(5/5\)3\.718queen13\_131693328170\.031180\.00216\(3/5\)4\.712queen14\_141964186190\.030200\.00317\(2/5\)7\.667queen15\_152255180210\.040210\.00319\(5/5\)11\.0queen16\_162566320230\.056210\.00420\(5/5\)14\.4mycielmyciel3112040\.00040\.0004\(5/5\)0\.024myciel4237150\.00050\.0005\(5/5\)0\.076myciel54723660\.00160\.0006\(5/5\)0\.403myciel69575570\.00570\.0007\(5/5\)63\.6myciel7191236080\.02480\.0018\(5/5\)1468\.9milesmiles25012838780\.00680\.0018\(5/5\)23\.1miles5001281170200\.009200\.00120\(5/5\)8\.289miles7501282113310\.012310\.00131\(5/5\)185\.6mugmug88\_18814640\.00240\.0004\(5/5\)17\.2mug88\_258814640\.00240\.0004\(5/5\)0\.753mug100\_110016640\.00340\.0004\(5/5\)17\.8mug100\_2510016640\.00340\.0004\(5/5\)13\.0mulsolmulsol\.i\.21883885310\.028310\.00231\(5/5\)38\.8mulsol\.i\.31843916310\.028310\.00231\(5/5\)46\.8FullIns1\-FullIns\_33010040\.00050\.0004\(5/5\)0\.1161\-FullIns\_49359350\.00460\.0005\(5/5\)19\.22\-FullIns\_35220150\.00160\.0005\(5/5\)0\.5673\-FullIns\_38034660\.00270\.0006\(5/5\)2\.506Insertions1\-Insertions\_46723250\.00250\.0005\(5/5\)0\.8152\-Insertions\_3377240\.00140\.0004\(5/5\)0\.1642\-Insertions\_414954150\.00850\.0015\(5/5\)5\.8513\-Insertions\_35611040\.00140\.0004\(5/5\)0\.4623\-Insertions\_4281104650\.02750\.0025\(5/5\)38\.9le450le450\_5a4505714100\.122110\.0097\(1/5\)32\.9le450\_5b450573490\.122100\.0097\(3/5\)30\.7le450\_5d4509757120\.168110\.0105\(5/5\)1912\.9le450\_15a4508168170\.160170\.01016\(5/5\)96\.5le450\_15b4508169160\.161160\.01016\(5/5\)454\.9le450\_15c45016680230\.260240\.01223\(5/5\)160\.5le450\_15d45016750240\.274260\.01323\(5/5\)112\.4le450\_25a4508260250\.173260\.00925\(5/5\)1471\.9le450\_25d45017425280\.281290\.01227\(2/5\)67\.0schoolschool138519095170\.242150\.01014\(5/5\)309\.4school1\_nsh35214612270\.166160\.00815\(5/5\)164\.8latin\_squarelatin\_square\_109003073501327\.2241340\.085122\(1/5\)91\.6
#### FAP Instances

Table 4:FAP instances results\.DSATURGISDSSLDInstance\|V\|\|V\|\|E\|\|E\|kkt⁡\(s\)t\(s\)kkt⁡\(s\)t\(s\)kk\(hit\)t⁡\(s\)t\(s\)CELARCELAR019165548120\.338130\.028T/O \(–\)3600CELAR022001235130\.017130\.00213\(5/5\)11\.1CELAR034002760130\.069120\.00612\(5/5\)911\.2CELAR046803967130\.190130\.016T/O \(–\)3600CELAR054002598120\.069120\.006T/O \(–\)3600CELAR062001322200\.016200\.00220\(5/5\)14\.5CELAR074002865200\.070200\.00620\(5/5\)660\.4CELAR116804103200\.197200\.017T/O \(–\)3600GRAPHGRAPH012001134180\.017180\.00218\(5/5\)267\.7GRAPH024002245140\.065140\.006T/O \(–\)3600GRAPH032001134120\.015120\.00212\(5/5\)166\.7GRAPH044002244140\.064140\.006T/O \(–\)3600GRAPH052001134180\.016180\.00218\(5/5\)262\.9GRAPH086803757160\.188160\.01516\(5/5\)1791\.0GRAPH099165246180\.358180\.026T/O \(–\)3600GRAPH14916463880\.31980\.0318\(5/5\)116\.0
#### Job Shop Scheduling Instances

Table 5:Job Shop Scheduling instances results\.DSATURGISDSSLDInstance\|V\|\|V\|\|E\|\|E\|kkt⁡\(s\)t\(s\)kkt⁡\(s\)t\(s\)kk\(hit\)t⁡\(s\)t\(s\)p\-instancesp06163840\.00040\.0004\(5/5\)0\.028p07249250\.00050\.0005\(5/5\)0\.073p08249250\.00050\.0005\(5/5\)0\.073p092510050\.00050\.0005\(5/5\)0\.045p10163240\.00040\.0004\(5/5\)0\.028p11184850\.00050\.0005\(5/5\)0\.035p12269050\.00050\.0005\(5/5\)0\.077p133416060\.00160\.0006\(5/5\)0\.133p143111060\.00160\.0006\(5/5\)0\.070p153413660\.00160\.0006\(5/5\)0\.141p163413460\.00160\.0006\(5/5\)0\.085p173716170\.00170\.0007\(5/5\)0\.100p183514360\.00170\.0006\(5/5\)0\.087p193615670\.00170\.0007\(5/5\)0\.121p203714260\.00160\.0006\(5/5\)0\.099p213815570\.00170\.0007\(5/5\)0\.103p223815460\.00160\.0006\(5/5\)0\.124p234420470\.00170\.0007\(5/5\)0\.132p243410460\.00160\.0006\(5/5\)0\.092r\-instancesr011441280130\.010130\.00113\(5/5\)1\.533r051421266130\.009130\.00113\(5/5\)1\.789r101501409130\.011130\.00113\(5/5\)1\.631r151982055160\.019160\.00216\(5/5\)3\.711GEOMGEOM30305060\.00060\.0006\(5/5\)0\.073GEOM505012760\.00160\.0006\(5/5\)0\.616GEOM10010054790\.004100\.0019\(5/5\)58\.5GEOM11011063890\.005100\.0019\(5/5\)34\.0GEOM120120773110\.006110\.00111\(5/5\)32\.3
#### Random Graphs

For each random graph family, we generaten=500n=500instances and report how SSLD compares against both DSATUR and GISD\. The wins column counts instances where SSLD uses fewer colors than the baseline, ties where it uses the same, and loss where it uses more\.Δavg\\Delta\_\{\\text\{avg\}\}is the mean color reductionkbaseline−kSSLDk\_\{\\text\{baseline\}\}\-k\_\{\\text\{SSLD\}\}computed over wins only, andΔmax\\Delta\_\{\\text\{max\}\}is the largest single improvement observed\.

Table 6:

### 5\.3Runtime & Performance Analysis

The SSLD algorithm is decomposed into two phases: one SDP solve andTTrounding iterations\. Each rounding iteration follows the randomized rounding procedure of Karger, Motwani, and Sudan\[[16](https://arxiv.org/html/2609.17633#bib.bib48)\]: a random projection is applied to the SDP embedding, followed by a greedy extraction of an independent set and a DSATUR completion\. We compare their respective runtimes\. Figure[3](https://arxiv.org/html/2609.17633#S5.F3)shows the SDP solve time as a function of the vertex count\|V\|\|V\|and the non\-edge count across the benchmark families\.

The diagonal of the matrixXXoptimized in the D\-SDP is pinned to11and every edge entry to00, so the free variables of the program are exactly the non\-adjacent pairs\. Solve time grows with both quantities, going from1\.2×10−21\.2\\times 10^\{\-2\}s on the smallest scheduling instances to1\.8×1031\.8\\times 10^\{3\}s on the largest FAP instances\.

Order is the strongest structural predictor since the solve time is growing roughly as\|V\|2\.4\|V\|^\{2\.4\}\. Because\|E\|¯\\overline\{\|E\|\}grows like\|V\|2\|V\|^\{2\}, it tells us nothing beyond\|V\|\|V\|, so the second panel reports how many free variables the program has rather than an independent cause of its cost\.

![Refer to caption](https://arxiv.org/html/2609.17633v1/fig_sdp_time_svg-tex.png)Figure 3:SDP solve time as a function of density across benchmark families\. One point per instance \(1604 in total\); axes logarithmic except for density\. The SDP solve time is defined per instance\.The rounding phase is not negligible atT=500T=500\. Over a single SSLD run, one SDP solve plus one rounding pass, the rounding accounts for a median of34\.7%34\.7\\%of total runtime \(mean34\.1%34\.1\\%, 90th percentile51\.2%51\.2\\%\) and it exceeds the SDP on280280of16041604instances \(17\.5%17\.5\\%\)\. The split is strongly family\-dependent, as Figure[4](https://arxiv.org/html/2609.17633#S5.F4)shows: rounding represents approximately0\.5%0\.5\\%of a run on the large FAP instances,22\.3%22\.3\\%on DIMACS,34\.8%34\.8\\%on the random graphs and45\.3%45\.3\\%on the small scheduling instances\. The SDP therefore dominates only where it is expensive in absolute terms\.

Figure 4:Runtime breakdown between the SDP solve and the rounding phase\. \(a\) median split per family\. \(b\) distribution of the rounding share across instances, boxes spanning the inter\-quartile range with whiskers at the 5th and 95th percentiles\. The dashed line marks where the two phases cost the same\.Figure[5](https://arxiv.org/html/2609.17633#S5.F5)illustrates the trade\-off between quality and runtime across all benchmark instances\. DSATUR and GISD are faster by two to three orders of magnitude: the median runtime is5\.3×10−45\.3\\times 10^\{\-4\}s for GISD and4\.2×10−34\.2\\times 10^\{\-3\}s for DSATUR, against0\.820\.82s for SSLD, a factor of195195over DSATUR\. Panel \(a\) alone cannot establish the quality claim sincekkranges from22to115115across instances while the three algorithms differ by well under one color, so their points nearly coincide on thekkaxis\. Panel \(b\) provides the paired evidence: against DSATUR, SSLD uses fewer colors on876876instances, the same number on726726instances, and more on22instances, for a mean of−0\.83\-0\.83colors; against GISD the record is988988/615615/11, for a mean of−0\.94\-0\.94colors\. SSLD is thus not intended to replace DSATUR in time\-critical settings, but rather to serve as a higher\-quality alternative when runtime is not the primary constraint\.

![Refer to caption](https://arxiv.org/html/2609.17633v1/fig_quality_vs_time_svg-tex.png)Figure 5:Solution quality vs runtime across all benchmark instances\. \(a\) one point per instance per algorithm; the large outlined marker is the per\-algorithm median\. Lower and further left is better\. \(b\) per\-instance paired difference in colors between SSLD and each baseline; negative values are instances where SSLD uses fewer colors\.

## 6Conclusion

We introduced SSLD, a preprocessing strategy for DSATUR that fixes a single color class chosen via an SDP before completing the coloring with DSATUR\. Across over 1600 benchmark instances considered, through the DIMACS and COLOR challenges, frequency assignment and job shop scheduling instances, the Spinrad–Vijayan adversarial family, and three synthetic random graph models, SSLD matches or improves on plain DSATUR in almost every case\.

GISD uses more colors than DSATUR on several instances, confirming that fixing an arbitrary color class first does not consistently help\. By contrast, SSLD uses fewer colors than DSATUR on 876 of the 1604 instances tested and fewer than GISD on 988 instances, with only 2 and 1 losses respectively\. This confirms that the gain is attributable specifically to the SDP\-guided choice of the first color class rather than to the simple act of fixing a color class before using DSATUR\.

This improvement in using fewer colors comes at a substantial runtime cost\. SSLD is roughly 195 times slower than DSATUR in median runtime, and this overhead is not confined to the SDP solve itself: the rounding phase that consists ofT=500T=500independent projections and DSATUR completions, accounts for a median of 34\.7% of total runtime and exceeds the cost of the SDP solve on 17\.5% of instances \(Section[5\.3](https://arxiv.org/html/2609.17633#S5.SS3)\)\. Since SSLD’s runtime grows with graph size and density, it causes timeouts on several CELAR and GRAPH instances\.

The embedding produced by the D\-SDP carries no mathematical guarantee that the independent sets extracted from it are optimal or even good as a first color class for DSATUR: while the D\-SDP objective encourages alignment of non\-adjacent vertices, nothing in the formulation ensures that the resulting random projections will result in an independent set that minimizes the number of colors DSATUR needs to complete the coloring\. Nevertheless, there is reason to believe that SDP\-based preprocessing can be made theoretically grounded\. Karger, Motwani and Sudan\[[16](https://arxiv.org/html/2609.17633#bib.bib48)\]did manage to show that an SDP relaxation linked to the Lovász theta function, combined with randomized rounding, results a polynomial\-time approximation algorithm for graph coloring with provable guarantees:O⁡\(n0\.387\)O\(n^\{0\.387\}\)colors on 3\-colorable graphs andO⁡\(n1−3/\(k\+1\)\)O\(n^\{1\-3/\(k\+1\)\}\)colors onkk\-colorable graphs\. Therefore, it is a future direction to attempt to establish whether the D\-SDP embedding can admit approximation guarantees\.

Several other directions are worth pursuing to build on this work\. The first one concerns the random projection step, we currently apply a blind search overTTattempts with no guidance on what makes a good directionrr, it could be replaced by a learned or locally\-optimized projection, which would help reducing wasted iterations\. More broadly, rather than fixing a single color class before using DSATUR, we could iteratively fix multiple color classes, each guided by the SDP embedding of the residual graph\. The rounding procedure itself could also be made smarter, for instance by combining multiple directions simultaneously or by biasing the projection using the previously obtained coloring\.

Finally, the SDP solve remains the dominant runtime cost on large instances; warm starting, exploiting sparsity, or replacing the SDP with a cheaper relaxation are potential directions to make SSLD practical on denser and larger graphs\.

## References

- \[1\]R\. Lewis\(2021\)Guide to graph colouring\.Springer\.External Links:[Document](https://dx.doi.org/https%3A//doi.org/10.1007/978-3-319-25730-3)Cited by:[§1](https://arxiv.org/html/2609.17633#S1.p1.1)\.
- \[2\]P\. Briggs, K\. D\. Cooper, K\. Kennedy, and L\. Torczon\(1989\)Coloring heuristics for register allocation\.Acm Sigplan Notices24\(7\),pp\. 275–284\.External Links:[Link](https://dl.acm.org/doi/pdf/10.1145/74818.74843)Cited by:[§1](https://arxiv.org/html/2609.17633#S1.p1.1)\.
- \[3\]G\. J\. Chaitin, M\. A\. Auslander, A\. K\. Chandra, J\. Cocke, M\. E\. Hopkins, and P\. W\. Markstein\(1981\)Register allocation via coloring\.Computer languages6\(1\),pp\. 47–57\.External Links:[Link](https://web.cs.ucla.edu/~harryxu/courses/142b/spring18/resource/register_allocation_via_coloring.pdf)Cited by:[§1](https://arxiv.org/html/2609.17633#S1.p1.1)\.
- \[4\]G\. J\. Chaitin\(1982\)Register allocation & spilling via graph coloring\.ACM Sigplan Notices17\(6\),pp\. 98–101\.External Links:[Link](https://dl.acm.org/doi/pdf/10.1145/872726.806984)Cited by:[§1](https://arxiv.org/html/2609.17633#S1.p1.1)\.
- \[5\]D\. C\. Wood\(1969\)A technique for colouring a graph applicable to large scale timetabling problems\.The Computer Journal12\(4\),pp\. 317–319\.Cited by:[§1](https://arxiv.org/html/2609.17633#S1.p1.1)\.
- \[6\]C\. Berge\(1985\)Graphs and hypergraphs\.Elsevier Science Ltd\.\.Cited by:[§1](https://arxiv.org/html/2609.17633#S1.p1.1),[§5\.1](https://arxiv.org/html/2609.17633#S5.SS1.SSSx3.p1.1)\.
- \[7\]M\. R\. Garey and D\. S\. Johnson\(2002\)Computers and intractability\.Vol\.29,wh freeman New York\.Cited by:[§1](https://arxiv.org/html/2609.17633#S1.p1.1)\.
- \[8\]E\. Lawler\(1976\)A note on the complexity of the chromatic number problem\.Ph\.D\. Thesis,IRIA\.Cited by:[§1](https://arxiv.org/html/2609.17633#S1.p2.1)\.
- \[9\]A\. Björklund, T\. Husfeldt, and M\. Koivisto\(2009\)Set partitioning via inclusion\-exclusion\.SIAM Journal on Computing39\(2\),pp\. 546–563\.Cited by:[§1](https://arxiv.org/html/2609.17633#S1.p2.1)\.
- \[10\]R\. Beigel and D\. Eppstein\(2005\)3\-coloring in time o \(1\.3289 n\)\.Journal of Algorithms54\(2\),pp\. 168–204\.Cited by:[§1](https://arxiv.org/html/2609.17633#S1.p2.1)\.
- \[11\]F\. V\. Fomin, S\. Gaspers, and S\. Saurabh\(2007\)Improved exact algorithms for counting 3\-and 4\-colorings\.InInternational Computing and Combinatorics Conference,pp\. 65–74\.Cited by:[§1](https://arxiv.org/html/2609.17633#S1.p2.1)\.
- \[12\]M\. Grötschel, L\. Lovász, and A\. Schrijver\(1984\)Polynomial algorithms for perfect graphs\.InNorth\-Holland mathematics studies,Vol\.88,pp\. 325–356\.Cited by:[§1](https://arxiv.org/html/2609.17633#S1.p2.1)\.
- \[13\]U\. Feige and J\. Kilian\(1998\)Zero knowledge and the chromatic number\.Journal of Computer and System Sciences57\(2\),pp\. 187–199\.Cited by:[§1](https://arxiv.org/html/2609.17633#S1.p3.1)\.
- \[14\]S\. Khot and A\. K\. Ponnuswami\(2006\)Better inapproximability results for maxclique, chromatic number and min\-3lin\-deletion\.InInternational Colloquium on Automata, Languages, and Programming,pp\. 226–237\.Cited by:[§1](https://arxiv.org/html/2609.17633#S1.p3.1)\.
- \[15\]D\. Johnson\(1974\)Worst case behavior of graph coloring algorithms\.InProceedings of the 5th Southeast Conference on Combinatorics, Graph Theory, and Computing, 1974,pp\. 513–527\.Cited by:[§1\.1](https://arxiv.org/html/2609.17633#S1.SS1.p1.1)\.
- \[16\]D\. Karger, R\. Motwani, and M\. Sudan\(1998\)Approximate graph coloring by semidefinite programming\.Journal of the ACM \(JACM\)45\(2\),pp\. 246–265\.External Links:[Link](https://dl.acm.org/doi/pdf/10.1145/274787.274791)Cited by:[§1\.1](https://arxiv.org/html/2609.17633#S1.SS1.p2.1),[§5\.3](https://arxiv.org/html/2609.17633#S5.SS3.p1.1),[§6](https://arxiv.org/html/2609.17633#S6.p4.1)\.
- \[17\]D\. Brélaz\(1979\)New methods to color the vertices of a graph\.Communications of the ACM22\(4\),pp\. 251–256\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p2.1)\.
- \[18\]F\. T\. Leighton\(1979\)A graph coloring algorithm for large scheduling problems\.Journal of research of the national bureau of standards84\(6\),pp\. 489\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p2.1)\.
- \[19\]J\.C\. Culberson and F\. Luo\(1996\)Exploring the k\-colorable landscape with iterated greedy\.DIMACS Series in Discrete Mathematics and Theoretical Computer Science26,pp\. 245––284\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p3.1)\.
- \[20\]D\. E\. Joslin and D\. P\. Clements\(1999\)Squeaky wheel optimization\.Journal of Artificial Intelligence Research10,pp\. 353–373\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p3.1)\.
- \[21\]M\. Laguna and R\. Martí\(2001\)A grasp for coloring sparse graphs\.Computational optimization and applications19\(2\),pp\. 165–178\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p3.1)\.
- \[22\]A\. Hertz and D\. de Werra\(1987\)Using tabu search techniques for graph coloring\.Computing39\(4\),pp\. 345–351\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p3.1)\.
- \[23\]R\. Dorne and J\. Hao\(1999\)Tabu search for graph coloring, t\-colorings and set t\-colorings\.InMeta\-heuristics: Advances and trends in local search paradigms for optimization,pp\. 77–92\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p3.1),[§5\.1](https://arxiv.org/html/2609.17633#S5.SS1.SSSx4.p3.1)\.
- \[24\]M\. Chams, A\. Hertz, and D\. De Werra\(1987\)Some experiments with simulated annealing for coloring graphs\.European Journal of Operational Research32\(2\),pp\. 260–266\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p3.1)\.
- \[25\]D\. S\. Johnson, C\. R\. Aragon, L\. A\. McGeoch, and C\. Schevon\(1991\)Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning\.Operations research39\(3\),pp\. 378–406\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p3.1)\.
- \[26\]M\. Chiarandini T\. Stützleet al\.\(2002\)An application of iterated local search to graph coloring problem\.InProceedings of the computational symposium on graph coloring and its generalizations,pp\. 112–125\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p3.1)\.
- \[27\]C\. Avanthay, A\. Hertz, and N\. Zufferey\(2003\)A variable neighborhood search for graph coloring\.European Journal of Operational Research151\(2\),pp\. 379–388\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p3.1)\.
- \[28\]C\. Morgenstern\(1996\)Distributed coloration neighborhood search\.Discrete Mathematics and Theoretical Computer Science26,pp\. 335–358\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p3.1)\.
- \[29\]G\. Lewandowski and A\. Condon\(1996\)Experiments with parallel graph coloring heuristics and applications of graph coloring\.Johnson and Trick \(1996\),pp\. 309–334\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p3.1)\.
- \[30\]I\. Blöchliger and N\. Zufferey\(2008\)A graph coloring heuristic using partial solutions and a reactive tabu scheme\.Computers & Operations Research35\(3\),pp\. 960–975\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p3.1)\.
- \[31\]S\. Prestwich\(2002\)Coloration neighbourhood search with forward checking\.Annals of Mathematics and Artificial Intelligence34\(4\),pp\. 327–340\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p3.1)\.
- \[32\]A\. Hertz, M\. Plumettaz, and N\. Zufferey\(2008\)Variable space search for graph coloring\.Discrete Applied Mathematics156\(13\),pp\. 2551–2560\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p3.1)\.
- \[33\]C\. Fleurent and J\. A\. Ferland\(1996\)Genetic and hybrid algorithms for graph coloring\.Annals of operations research63\(3\),pp\. 437–461\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p4.1)\.
- \[34\]R\. Dorne and J\. Hao\(1998\)A new genetic local search algorithm for graph coloring\.InInternational Conference on Parallel Problem Solving from Nature,pp\. 745–754\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p4.1)\.
- \[35\]P\. Galinier and J\. Hao\(1999\)Hybrid evolutionary algorithms for graph coloring\.Journal of combinatorial optimization3\(4\),pp\. 379–397\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p4.1)\.
- \[36\]P\. Galinier, A\. Hertz, and N\. Zufferey\(2008\)An adaptive memory algorithm for the k\-coloring problem\.Discrete Applied Mathematics156\(2\),pp\. 267–279\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p4.1)\.
- \[37\]E\. Malaguti, M\. Monaci, and P\. Toth\(2008\)A metaheuristic approach for the vertex coloring problem\.INFORMS Journal on Computing20\(2\),pp\. 302–316\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p4.1),[§5\.1](https://arxiv.org/html/2609.17633#S5.SS1.SSSx2.p3.1),[§5\.1](https://arxiv.org/html/2609.17633#S5.SS1.SSSx4.p3.1)\.
- \[38\]D\. C\. Porumbel, J\. Hao, and P\. Kuntz\(2009\)Diversity control and multi\-parent recombination for evolutionary graph coloring algorithms\.InEuropean Conference on Evolutionary Computation in Combinatorial Optimization,pp\. 121–132\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p4.1)\.
- \[39\]Z\. Lü and J\. Hao\(2010\)A memetic algorithm for graph coloring\.European Journal of Operational Research203\(1\),pp\. 241–250\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p4.1)\.
- \[40\]W\. Sun, J\. Hao, Y\. Zang, and X\. Lai\(2021\)A solution\-driven multilevel approach for graph coloring\.Applied Soft Computing104,pp\. 107174\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p5.1),[§5\.1](https://arxiv.org/html/2609.17633#S5.SS1.SSSx4.p3.1)\.
- \[41\]D\. C\. Porumbel, J\. Hao, and P\. Kuntz\(2010\)A search space “cartography” for guiding graph coloring heuristics\.Computers & Operations Research37\(4\),pp\. 769–778\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p5.1)\.
- \[42\]F\. Glover, M\. Parker, and J\. Ryan\(1996\)Coloring by tabu branch and bound\.DIMACS Series in Discrete Mathematics and Theoretical Computer Science26,pp\. 285–307\.Cited by:[§1\.2](https://arxiv.org/html/2609.17633#S1.SS2.p5.1)\.
- \[43\]L\. Lovász\(1979\)On the shannon capacity of a graph\.IEEE Transactions on Information theory25\(1\),pp\. 1–7\.Cited by:[§1\.3](https://arxiv.org/html/2609.17633#S1.SS3.SSS0.Px3),[§1\.3](https://arxiv.org/html/2609.17633#S1.SS3.p1.1),[§1\.4](https://arxiv.org/html/2609.17633#S1.SS4.p5.1)\.
- \[44\]M\. Grötschel, L\. Lovász, and A\. Schrijver\(1981\)The ellipsoid method and its consequences in combinatorial optimization\.Combinatorica1\(2\),pp\. 169–197\.External Links:[Link](https://link.springer.com/content/pdf/10.1007/BF02579273.pdf)Cited by:[§1\.4](https://arxiv.org/html/2609.17633#S1.SS4.p2.1)\.
- \[45\]D\. S\. Johnson and M\. A\. Trick\(1996\)Cliques, coloring, and satisfiability: second dimacs implementation challenge, october 11\-13, 1993\.Vol\.26,American Mathematical Soc\.\.Cited by:[§5\.1](https://arxiv.org/html/2609.17633#S5.SS1.SSSx2.p1.1),[§5\.1](https://arxiv.org/html/2609.17633#S5.SS1.SSSx3.p1.1),[§5\.1](https://arxiv.org/html/2609.17633#S5.SS1.p1.1)\.
- \[46\]P\. Erdős and A\. Rényi\(1959\)On random graphs i\.Publ\. math\. debrecen6\(290\-297\),pp\. 18\.Cited by:[1st item](https://arxiv.org/html/2609.17633#S5.I1.i1.p1.1),[§5\.1](https://arxiv.org/html/2609.17633#S5.SS1.p1.1)\.
- \[47\]D\. J\. Watts and S\. H\. Strogatz\(1998\)Collective dynamics of ‘small\-world’networks\.nature393\(6684\),pp\. 440–442\.Cited by:[2nd item](https://arxiv.org/html/2609.17633#S5.I1.i2.p1.1),[§5\.1](https://arxiv.org/html/2609.17633#S5.SS1.p1.1)\.
- \[48\]A\. Barabási and R\. Albert\(1999\)Emergence of scaling in random networks\.science286\(5439\),pp\. 509–512\.Cited by:[3rd item](https://arxiv.org/html/2609.17633#S5.I1.i3.p1.1),[§5\.1](https://arxiv.org/html/2609.17633#S5.SS1.p1.1)\.
- \[49\]J\. P\. Spinrad and G\. Vijayan\(1985\)Worst case analysis of a graph coloring algorithm\.Discrete Applied Mathematics12\(1\),pp\. 89–92\.Cited by:[§5\.1](https://arxiv.org/html/2609.17633#S5.SS1.SSSx1.p1.1),[§5\.1](https://arxiv.org/html/2609.17633#S5.SS1.p1.1)\.