Pith. sign in

REVIEW 3 major objections 5 minor 69 references

HyColor: An Efficient Heuristic Algorithm for Graph Coloring

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read HyColor, a hybrid heuristic combining clique-based lower bounds, degree-based reduction, and k-core greedy coloring, is claimed to match or beat three leading graph coloring algorithms on 194 of 209 benchmarks within a 60-second budget.

desk verdict A competent graph-coloring heuristic with a sound reduction proof and broad benchmarks, but the headline advantage is likely inflated by tuning alpha on the same test suite. read the letter →

arxiv 2506.07373 v1 pith:ET2OQ23F submitted 2025-06-09 cs.DM cs.AI

Enqiang Zhu , Yu Zhang , Haopeng Sun , Ziqi Wei , Witold Pedrycz , Chanjuan Liu , Jin Xu This is my paper
classification cs.DMcs.AI MSC 05C1568R1090C59
keywords graphcoloringheuristicalgorithmchromaticnumberk-coredecompositionreductionmixeddegreelarge-scalegraphslowerbound
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

HyColor is a hybrid heuristic for the graph coloring problem aimed at a gap in the literature: algorithms that work well on small dense graphs struggle on large sparse networks, and vice versa. The paper claims that a loop joining three components — a clique-based lower-bound finder, a lower-bound-driven graph reduction, and a k-core and mixed-degree greedy coloring — produces colorings within a 60-second budget that use no more colors than FASTCOLOR, LS+I-DSATUR, and GC-SLIM on 194 of 209 benchmark instances, strictly fewer colors on 34, and provably optimal colorings on 128. If the claim holds, a single configuration of one heuristic, without per-benchmark tuning, can serve both large sparse networks and small dense graphs where previously the best tools split into two camps.

What carries the argument

The engine of the algorithm is the loop between a lower bound $\ell$ and an upper bound $k$ on the chromatic number $\chi(G)$. FINDCLQ, a simplification of a maximum-weight-clique heuristic, finds a clique whose size lower-bounds $\chi(G)$; EXACTLB grows a dense test subgraph around a maximum-degree vertex and calls an industrial solver on it, returning a larger clique as the new lower bound whenever the test set stays below 1000 vertices, with a 1-second budget per call. Each time the lower bound rises, REDURULE deletes every vertex of degree less than $\ell$ (an $\ell^-$-vertex), recomputing degrees dynamically and pushing the deleted vertices onto a stack; Proposition 2 guarantees that a $k$-coloring of the reduced graph extends to a coloring of the original graph with at most $\max\{\ell, k\}$ colors, which is the BF-Rule applied at the end. MDDCOLOR then colors the reduced graph, ordering vertices by shell number from k-core decomposition and, with probability $\alpha$, reordering within each core layer by mixed degree (a weighted count of remaining and already-removed neighbors, weight 0.7); a recoloring step suppresses new colors, and DSATUR replaces MDDCOLOR in later iterations when the working graph has not been reduced.

What would settle it

Fix $\alpha = 0.2$ before any testing and run HyColor on large sparse graphs outside the four reported benchmarks — for instance, newly published network datasets or random power-law graphs with controlled degree distributions — under the same 60-second cutoff, counting how often it matches or beats FASTCOLOR and LS+I-DSATUR. If the match-or-beat rate falls well below the reported 194 of 209 and the strictly-better count collapses, the in-sample choice of $\alpha$ explains the gap; if the rate holds on fresh graphs, the claim transfers.

Watch

Extended reading notes

Core claim

The central claim is that HyColor, run ten times per instance with a 60-second cutoff, matches or beats three leading heuristics — FASTCOLOR, LS+I-DSATUR, and GC-SLIM — on the majority of 209 instances drawn from four benchmarks: the small dense DIMACS graphs and the large sparse DIMACS10, SNAP, and Network Data Repository graphs. The paper reports that HyColor uses no more colors than all three baselines on 194 instances (over 93%), strictly fewer colors on 34 of them, and certifies the optimal chromatic number on 128 instances by closing the gap between its lower and upper bounds. The paper attributes this behavior to the interaction of three mechanisms: a lower-bound refinement that searches for larger cliques in small dense subgraphs, a reduction rule that deletes every vertex of degree below the current lower bound, and a greedy coloring that orders vertices by k-core shell number and mixed degree. The same loop produces optimality certificates, since the algorithm stops when the lower bound meets the upper bound.

Load-bearing premise

The load-bearing premise is that picking the reordering probability $\alpha = 0.2$ by scanning candidate values on the same four benchmarks that the paper then uses to report its 194-of-209 advantage gives a fair estimate of HyColor's general performance; if that choice overfits this particular suite, the headline advantage over the baselines may not transfer to other graphs.

Editorial extensions

If this is right

  • A single fixed configuration of HyColor ($\alpha = 0.2$) is claimed to match or beat FASTCOLOR, LS+I-DSATUR, and GC-SLIM on 194 of 209 benchmark instances, so practitioners coloring large sparse networks can expect fewer colors than the previous best sparse-graph heuristics within the same 60-second budget.
  • The lower-bound loop closes the gap to optimality on 128 instances, certifying the chromatic number; for those graphs the result is a proof of optimality, not just a good heuristic value.
  • GC-SLIM's adjacency-matrix storage stops it near 280,000 vertices under 128 GB of memory, while HyColor keeps running on the largest instances in the suite, so the method extends practical coloring to graphs the dense-graph specialist cannot even load.
  • Statistical tests reported by the paper (Friedman p-value $6.4 \times 10^{-28}$ and a Nemenyi critical difference of about 0.32) support the claim that HyColor's average rank across the 209 instances differs significantly from each baseline.
  • Ablation of any one of the three components — REDURULE, MDD ordering, or EXACTLB — is reported to worsen average color counts, indicating each contributes to the overall result rather than one dominating the others.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The 194-best count is measured on the same benchmarks used to pick $\alpha = 0.2$, so the honest reading is that HyColor is well tuned to this specific suite; the open question is how much of the advantage survives on graphs outside DIMACS10, SNAP, and the Network Data Repository, which a held-out test would settle.
  • Because REDURULE deletes vertices whose degree is below the current lower bound, its leverage should be largest on graphs with a broad low-degree periphery (typical of power-law networks) and near zero on regular graphs; if that is right, HyColor's edge over FASTCOLOR on regular or near-regular sparse graphs would come down to the MDD ordering and recoloring alone.
  • The same lower-bound, reduction, and greedy-coloring loop transfers naturally to partition coloring and total coloring, which the paper names as future work, and to maximum clique computation itself, since FINDCLQ and EXACTLB already produce the cliques that drive the lower bound.
  • EXACTLB spends its 1-second solver budget on dense subgraphs around high-degree vertices; a variant that targeted the densest core layers or used a cheaper clique heuristic could trade lower-bound strength for speed on graphs where the 60-second cutoff binds, a trade-off the paper does not explore.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes HyColor, a hybrid heuristic for the graph coloring problem that combines a clique-based lower bound (FindClq plus an ExactLB procedure invoking Gurobi on dense subgraphs), a reduction rule that deletes vertices of degree below the current lower bound, and a k-core/mixed-degree greedy coloring procedure. The algorithm is compared against FASTCOLOR, LS+I-DSATUR, and GC-SLIM on 209 instances from four benchmarks, with ten seeds per instance and a 60-second cutoff. The main reported results are that HyColor matches or beats all baselines on 194 instances, is strictly better on 34 instances, and certifies an optimal coloring on 128 instances. The paper also reports Friedman and Nemenyi tests and a parameter-sensitivity study for the probability parameter alpha.

Significance. The paper contains a well-defined reduction-extension argument: Proposition 2 correctly shows that any coloring of the reduced graph extends to a coloring of the original graph with no more than max(lb, k) colors, and Theorem 1 gives a plausible O(m + n^2) bound for MDDCOLOR. The benchmark coverage is broad for the heuristic graph-coloring literature, and the use of ten seeds per instance plus non-parametric statistical tests is a strength. If the empirical claims remained valid after correcting the evaluation protocol, HyColor would be a genuinely useful contribution, particularly for large sparse graphs. However, the headline generalization is currently weakened by in-sample parameter selection, by incomplete handling of baseline runs that returned no solution, and by an unsupported efficiency claim.

major comments (3)
  1. [V-B and V-I, Figure 4] The value alpha = 0.2 is chosen by scanning alpha from 0.1 to 1.0 on the same four benchmarks used to produce Tables II-VI, and the same benchmark suite is then used for the headline counts. Section V-B states that alpha is set 'according to Section V-I', and Section V-I reports that alpha = 0.2 yielded the best performance in that scan. Because FASTCOLOR, LS+I-DSATUR, and GC-SLIM receive no analogous tuning, the reported 194-best and 34-strictly-better counts are in-sample summaries rather than unbiased estimates of out-of-sample performance. Please report the full rank spread across alpha values, and either adopt a separate tuning set, cross-validation, or a sensitivity analysis showing that the qualitative conclusions are stable for neighboring alpha values. Without this, the claim that HyColor 'consistently outperforms' the baselines is overstated.
  2. [V-H and Tables III-VI] The Friedman and Nemenyi tests are run with N = 209, but GC-SLIM is reported as N/A on many large instances in Tables III-VI due to its adjacency-matrix memory requirements. The paper does not state how these missing values were treated in the ranking procedure. If N/A entries were assigned a worst-case rank, the test is biased against GC-SLIM; if they were excluded, then N should reflect only instances where all four algorithms produced a value, and the critical difference should be recalculated. Please clarify the missing-data handling and rerun the statistical test on the subset of instances where all algorithms terminate, or use a procedure that explicitly accounts for missing observations. The summary counts of 'best' solutions should likewise be qualified as 'best among algorithms that returned a solution'.
  3. [V-B and Abstract] The abstract claims that HyColor outperforms existing algorithms in both solution accuracy and computational efficiency, but the main text does not contain a runtime table. Tables II-VI report only Min(Avg) numbers of colors, and the average time to reach the best solution is deferred to the supplementary materials. Since 'computational efficiency' is part of the central claim, please include at least a summary runtime table in the main text—for example, average or median time to best solution and total cutoff consumption per benchmark—or temper the efficiency claim to what the reported data actually support.
minor comments (5)
  1. [IV-A, Algorithm 2] The prose says the test set is initialized as N_Gk[u], while the pseudocode on line 1 initializes it as N_Gk(u), leaving u out of the test set. Please correct the pseudocode or the text so that the described procedure and the implementation match.
  2. [Table VII] The column headings are difficult to parse because the '<', '<=', and '*' symbols are not clearly aligned with the four algorithm names. Please restructure the header, and correct the repeated typo 'GC-LSIM' to 'GC-SLIM'.
  3. [V-B] The phrase 'according to Section V-I' refers to a later section; please ensure the cross-reference is unambiguous. Also, 'Algorthm 1' in the same section is a typo.
  4. [V-G] The text uses 'LS+I-DSATUR+' with a stray plus sign; please remove it.
  5. [V-I, Figure 4] The body text for Figure 4 contains raw encoded strings instead of a legible figure. The figure should be embedded properly in the submission.

Circularity Check

1 steps flagged · score 4.0 of 10

α is tuned on the same 209 instances used for the headline comparisons, so the reported superiority counts are in-sample model-selection results rather than independent evidence.

  1. fitted input called prediction [Section V-B (Experimental Settings) and Section V-I (Effects of Different Parameter Settings)]
    "The parameters for FASTCOLOR, LS+I-DSATUR, and GC-SLIM were set according to their default values, and the parameter α in HYCOLOR (Algorthm 1) was set to 0.2 according to Section V-I. ... For each parameter setting, we ran HYCOLOR ten times with a time limit of 60 seconds, recording the 'Min' and 'Avg' ranks achieved on each benchmark. The average ranking was then used to evaluate overall performance. ... it appears that α = 0.2 yielded the best performance, prompting us to configure α for HYCOLOR at this optimal value."

    The same 209 instances and the same ten-run/60-second protocol are used both to select α, by scanning 0.1 through 1.0 and retaining the best average rank, and to produce the headline comparisons in Tables II–VII, including the 194-best, 34-strictly-better, and 128-optimal counts and the Friedman p-value. Thus the reported advantage is the in-sample value of the selected configuration, not an out-of-sample estimate. A parameter chosen as the best of ten candidates on the test suite is expected to look better than fixed baselines even if all α values are equivalent, and the paper reports neither the rank spread across α values nor a separate tuning set. The 194/34 counts are therefore partly forced by the selection step rather than being independent evidence of HyColor's general superiority.

full rationale

The mathematical and algorithmic core of the paper is not circular: Proposition 2 is proved directly from the definition of the deletion rule, Theorem 1 is a standard complexity argument, and the reduction, lower-bound, and greedy-coloring components are described as constructive procedures rather than being assumed from the result they are used to support. The paper's self-citations are limited to related work and are not load-bearing for the main claim. The only material circularity is in the evaluation protocol: Section V-I selects α=0.2 by testing α on the exact four benchmarks that are later used in Section V-B to report the headline performance against FASTCOLOR, LS+I-DSATUR, and GC-SLIM. Because the baselines are run with default parameters and receive no analogous tuning, the reported 194-best and 34-strictly-better counts are in-sample model-selection results. The central derivation remains self-contained, but the central empirical claim of consistent superiority is partly a fitted-input comparison, so the score is moderate rather than zero.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

No invented entities are introduced. The central result is an algorithmic method, not a physical derivation. The method carries four tuned numerical parameters, one of which (alpha) is fit on the same benchmarks used for the headline comparison, and another (lambda) is borrowed from prior work. The main correctness statements are standard graph-coloring bounds plus a reduction-extension proof.

free parameters (4)
  • alpha = 0.2
    Probability of applying MDD reordering within a core layer. Tuned on the same four benchmark suites in Section V-I, Figure 4, then used for all headline results.
  • lambda = 0.7
    Weight coefficient in the mixed-degree formula, taken from reference [61]. Central to the MDD vertex ordering but not tuned in this paper.
  • size_upper = 1000
    Threshold for invoking Gurobi inside ExactLB. Chosen in Section IV-A because common hard graphs have fewer than 1000 vertices; directly affects how much lower-bound search is attempted.
  • Gurobi_time_limit = 1 second
    Per-call timeout for Gurobi in ExactLB, set in Section IV-A to make the solver return a feasible clique quickly. Affects the quality of the lower bound found.
assumptions (6)
  • standard math A clique in an induced subgraph of the working graph is a clique in the whole graph, so its size is a valid lower bound on the chromatic number.
    Used by FindClq and ExactLB in Section IV-A; follows from Proposition 1.
  • standard math Deleting all ell-minus vertices simultaneously is equivalent, for later coloring extension, to deleting them sequentially in some order, because vertex degrees only decrease after deletions.
    Needed to reconcile Algorithm 3 with the ordering argument in Proposition 2, Section IV-B.
  • domain assumption Gurobi returns a correct clique of the induced subgraph within the given one-second time limit.
    ExactLB depends on Gurobi output for lower-bound improvements, Section IV-A; no verification of Gurobi configurations or solution certificates is supplied.
  • domain assumption The four benchmarks DIMACS, DIMACS10, SNAP, and Network Data Repository are representative of the target class of graphs, and the 60-second cutoff is fair across algorithms.
    The main quantitative claims and the Friedman and Nemenyi tests generalize from these 209 instances, Section V-A and V-B.
  • domain assumption The baseline implementations and default parameters used for FASTCOLOR, LS+I-DSATUR, and GC-SLIM are appropriate state-of-the-art reference points.
    Fairness of the comparison rests on this premise, Section V-B; no independent replication or configuration audit is provided.
  • domain assumption The mixed-degree coefficient lambda=0.7 from reference [61], originally used for identifying influential spreaders, carries over usefully to graph coloring ordering.
    MDDCOLOR uses this external coefficient in Section IV-C; its suitability for coloring is assumed rather than demonstrated in this paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of HyColor: An Efficient Heuristic Algorithm for Graph Coloring." pith.science (2026). https://pith.science/paper/ET2OQ23F

@misc{pith2026250607373,
  author       = {Pith},
  title        = {Pith review of: HyColor: An Efficient Heuristic Algorithm for Graph Coloring},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ET2OQ23F}},
  note         = {Machine review of arXiv:2506.07373}
}
read the original abstract

The graph coloring problem (GCP) is a classic combinatorial optimization problem that aims to find the minimum number of colors assigned to vertices of a graph such that no two adjacent vertices receive the same color. GCP has been extensively studied by researchers from various fields, including mathematics, computer science, and biological science. Due to the NP-hard nature, many heuristic algorithms have been proposed to solve GCP. However, existing GCP algorithms focus on either small hard graphs or large-scale sparse graphs (with up to 10^7 vertices). This paper presents an efficient hybrid heuristic algorithm for GCP, named HyColor, which excels in handling large-scale sparse graphs while achieving impressive results on small dense graphs. The efficiency of HyColor comes from the following three aspects: a local decision strategy to improve the lower bound on the chromatic number; a graph-reduction strategy to reduce the working graph; and a k-core and mixed degree-based greedy heuristic for efficiently coloring graphs. HyColor is evaluated against three state-of-the-art GCP algorithms across four benchmarks, comprising three large-scale sparse graph benchmarks and one small dense graph benchmark, totaling 209 instances. The results demonstrate that HyColor consistently outperforms existing heuristic algorithms in both solution accuracy and computational efficiency for the majority of instances. Notably, HyColor achieved the best solutions in 194 instances (over 93%), with 34 of these solutions significantly surpassing those of other algorithms. Furthermore, HyColor successfully determined the chromatic number and achieved optimal coloring in 128 instances.

Figures

Figures reproduced from arXiv: 2506.07373 by the authors.

Figure 1
Figure 1. A graph G on 13 vertices C. MDDCOLOR Algorithm Observe that using the greedy heuristic to color a graph depends heavily on a vertex ordering chosen for coloring the vertices individually. A suitable order can significantly reduce the number of colors the greedy coloring uses. Theoretically, there is always an ordering (called optimal ordering) based on [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Visualization of Summary Results TABLE VII SUMMARY RESULTS Benchmark FASTCOLOR LS+I-DSATUR GC-LSIM HYCOLOR < <= ∗ < <= ∗ < <= < <= ∗ DIMACS 1 9 1 2 6 1 4 11 2 11 1 DIMACS10 3 29 20 0 24 6 3 11 4 30 23 SNAP 0 17 10 0 15 1 0 8 5 22 11 NDR 0 99 83 1 91 15 1 77 23 131 93 Total 4 154 114 3 136 23 8 107 34 194 128 H. Statistical Test To evaluate the performance differences between our pro￾posed algorithm, HYCOLOR, and the… view at source ↗
Figure 3
Figure 3. Statistic results with the Nemenyi test among four algorithms across [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Effects of Different Parameter Settings [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: Effects of ReduRule and MDD Components 0 20 40 60 80 100 120 Iteration Number 4 5 6 7 Lower Bound soc-wiki-Vote WITHOUT_EXACTLB HYCOLOR 0 20 40 60 80 100 120 140 Iteration Number 16 18 20 22 24 26 Lower Bound p_hat300-2 WITHOUT_EXACTLB HYCOLOR 0 10 20 30 40 50 60 70 80…
Figure 6
Figure 6. Figure 6: Effects of ExactLB Component partition coloring and total coloring, which present additional challenges, especially in the context of large-scale graphs. Developing optimization algorithms to tackle these problems represents a considerable challenge, and the concepts a…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

69 extracted references · 64 canonical work pages

  1. [1]

    Optimization of smart sensor for balance between code bug ratio and energy consumption,

    C. Hou, “Optimization of smart sensor for balance between code bug ratio and energy consumption,” IEEE Transactions on Systems, Man, and Cybernetcis-Systems, vol. 53, no. 1, pp. 451–461, 2023

    work page 2023

  2. [2]

    Local model- based pareto front estimation for multiobjective optimization,

    Y . Tian, L. Si, X. Zhang, K. C. Tan, and Y . Jin, “Local model- based pareto front estimation for multiobjective optimization,” IEEE Transactions on Systems, Man, and Cybernetcis-Systems , vol. 53, no. 1, pp. 623–634, 2023

    work page 2023

  3. [3]

    Matrix representation and behavioral analysis in a graph model for conflict resolution with incomplete fuzzy preferences,

    N. Wu, Y . Xu, H. Wang, and D. M. Kilgour, “Matrix representation and behavioral analysis in a graph model for conflict resolution with incomplete fuzzy preferences,” IEEE Transactions on Systems, Man, and Cybernetcis-Systems, p. r 10.1109/TSMC.2023.3307362, 2023

    arXiv

  4. [4]

    New methods to color the vertices of a graph. communica- tion,

    D. Brelaz, “New methods to color the vertices of a graph. communica- tion,” 1979

    work page 1979

  5. [5]

    Ore, The Four-color problem

    O. Ore, The Four-color problem. Academic Press, New York, 1969

    work page 1969

  6. [6]

    Haj ´os’ graph-coloring conjecture: variations and counterexam- ples,

    C. P. A, “Haj ´os’ graph-coloring conjecture: variations and counterexam- ples,” Journal of Combinatorial Theory Series B , vol. 26, pp. 268–274, 1979

    work page 1979

  7. [7]

    A new short proof of kneser’s conjecture,

    J. E. Greene, “A new short proof of kneser’s conjecture,” The American mathematical monthly, vol. 109, no. 10, pp. 918–920, 2002

    work page 2002

  8. [8]

    Optimality clue for graph coloring prob- lem,

    A. Gondran and L. Moalic, “Optimality clue for graph coloring prob- lem,” in International Conference on Integration of Constraint Program- ming, Artificial Intelligence, and Operations Research . Springer, 2019, pp. 337–354

    work page 2019

Show all 69 references
  1. [9]

    Graph coloring via neural networks for haplotype assembly and viral quasispecies reconstruction,

    H. Xue, V . Rajan, and Y . Lin, “Graph coloring via neural networks for haplotype assembly and viral quasispecies reconstruction,” Advances in Neural Information Processing Systems, NeurIPS 2022 , vol. 35, pp. 30 898–30 910, 2022

    2022

  2. [10]

    A hierarchical event de- tection method based on spectral theory of multidimensional matrix for power system,

    D. Ma, X. Hu, H. Zhang, Q. Sun, and X. Xie, “A hierarchical event de- tection method based on spectral theory of multidimensional matrix for power system,” IEEE Transactions on Systems, Man, and Cybernetcis- Systems, vol. 51, no. 4, pp. 2173–2186, 2021

    2021

  3. [11]

    A review of application of graph theory for network,

    A. Sadavare and R. Kulkarni, “A review of application of graph theory for network,” International Journal of Computer Science and Information Technologies, vol. 3, no. 6, pp. 5296–5300, 2012

    2012

  4. [12]

    Scalable design of error-correcting output codes using discrete optimization with graph coloring,

    S. Gupta and S. Amin, “Scalable design of error-correcting output codes using discrete optimization with graph coloring,” in Advances in Neural Information Processing Systems, NeurIPS 2022 , 2022

    2022

  5. [13]

    An effective solution space clipping-based algorithm for large-scale permutation flow shop scheduling problem,

    Y . Li, X. Li, and L. Gao, “An effective solution space clipping-based algorithm for large-scale permutation flow shop scheduling problem,” IEEE Transactions on Systems, Man, and Cybernetcis-Systems , vol. 53, no. 1, pp. 635–646, 2023

    2023

  6. [14]

    Partition independent set and reduction-based approach for partition coloring problem,

    E. Zhu, F. Jiang, C. Liu, and J. Xu, “Partition independent set and reduction-based approach for partition coloring problem,” IEEE Trans- actions on Cybernetics , vol. 52, no. 6, pp. 4960–4969, 2022

    2022

  7. [15]

    M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness . Freeman, San Francisco, CA, USA, 1979

    1979

  8. [16]

    Priority-based heuristics for the multi-skill resource constrained project scheduling problem,

    B. F. Almeida, I. Correia, and F. Saldanha-da Gama, “Priority-based heuristics for the multi-skill resource constrained project scheduling problem,” Expert Systems with Applications , vol. 57, pp. 91–103, 2016

    2016

  9. [17]

    Linear degree extractors and the inapproximability of max clique and chromatic number,

    D. Zuckerman., “Linear degree extractors and the inapproximability of max clique and chromatic number,” Theory of Computing, vol. 3, no. 1, pp. 103–128, 2007

    2007

  10. [18]

    3-coloring in time o(1.3289n),

    R. Beigel and D. Eppstein, “3-coloring in time o(1.3289n),” Journal of Algorithms, vol. 54, no. 2, pp. 168–204, 2005

    2005

  11. [19]

    Improved exact algorithms for counting 3-and 4-colorings,

    F. V . Fomin, S. Gaspers, and S. saurabh, “Improved exact algorithms for counting 3-and 4-colorings,” in International Computing and Com- binatorics Conference, 2007, pp. 65–74

    2007

  12. [20]

    Exact algorithms for counting 3-colorings of graphs,

    E. Zhu, P. Wu, and Z. Shao, “Exact algorithms for counting 3-colorings of graphs,” Discrete Applied Mathematics , vol. 322, pp. 74–93, 2022

    2022

  13. [21]

    The structure and function of complex networks,

    M. E. Newman, “The structure and function of complex networks,” SIAM review, vol. 45, no. 2, pp. 167–256, 2003

    2003

  14. [22]

    New techniques for approximating optimal substructure problems in power-law graphs,

    Y . Shen, D. T. Nguyen, Y . Xuan, and M. T. Thai, “New techniques for approximating optimal substructure problems in power-law graphs,” Theoretical Computer Science , vol. 447, pp. 107–119, 2012

    2012

  15. [23]

    Informed reactive tabu search for graph coloring,

    D. C. Porumbel, J.-K. Hao, and P. Kuntz, “Informed reactive tabu search for graph coloring,” Asia-Pacific Journal of Operational Research , vol. 30, no. 04, p. 1350010, 2013. 14

    2013

  16. [24]

    An improved dsatur-based branch-and-bound algorithm for the vertex coloring problem,

    F. Furini, V . Gabrel, and I.-C. Ternier, “An improved dsatur-based branch-and-bound algorithm for the vertex coloring problem,” Networks, vol. 69, no. 1, pp. 124–141, 2017

    2017

  17. [25]

    An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs,

    O. S ¸eker, T. Ekim, and Z. C. Tas ¸kın, “An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs,” European Journal of Operational Research , vol. 291, no. 1, pp. 67–83, 2021

    2021

  18. [26]

    A cuckoo quantum evolutionary algorithm for the graph coloring problem,

    Y . Xu and Y . Chen, “A cuckoo quantum evolutionary algorithm for the graph coloring problem,” in Bio-Inspired Computing: Theories and Ap- plications: 16th International Conference, BIC-TA 2021, Taiyuan, China, December 17–19, 2021, Revised Selected Papers, Part I. Springer, 2...

    2021

  19. [27]

    New evolutionary operators in coloring dimacs challenge benchmark graphs,

    R. Marappan and S. Bhaskaran, “New evolutionary operators in coloring dimacs challenge benchmark graphs,” International Journal of Informa- tion Technology, vol. 14, no. 6, pp. 3039–3046, 2022

    2022

  20. [28]

    Memetic teaching–learning-based opti- mization algorithms for large graph coloring problems,

    T. Dokeroglu and E. Sevinc, “Memetic teaching–learning-based opti- mization algorithms for large graph coloring problems,” Engineering Applications of Artificial Intelligence , vol. 102, p. 104282, 2021

    2021

  21. [29]

    Sat-boosted tabu search for coloring massive graphs,

    A. Schidler and S. Szeider, “Sat-boosted tabu search for coloring massive graphs,” ACM Journal of Experimental Algorithmics , vol. 28, pp. 1–19, 2023

    2023

  22. [30]

    A hybrid approach for exact coloring of massive graphs,

    E. Hebrard and G. Katsirelos, “A hybrid approach for exact coloring of massive graphs,” in International Conference on Integration of Con- straint Programming, Artificial Intelligence, and Operations Research . Springer, 2019, pp. 374–390

    2019

  23. [31]

    Coloring large complex networks,

    R. A. Rossi and N. K. Ahmed, “Coloring large complex networks,” Social Network Analysis and Mining , vol. 4, no. 1, pp. 1–37, 2014

    2014

  24. [32]

    Solving the maximum clique and vertex coloring problems on very large sparse networks,

    A. Verma, A. Buchanan, and S. Butenko, “Solving the maximum clique and vertex coloring problems on very large sparse networks,” INFORMS Journal on computing , vol. 27, no. 1, pp. 164–177, 2015

    2015

  25. [33]

    A reduction based method for coloring very large graphs,

    J. Lin, S. Cai, C. Luo, and K. Su, “A reduction based method for coloring very large graphs,” in IJCAI, 2017, pp. 517–523

    2017

  26. [34]

    Using tabu search techniques for graph coloring,

    A. Hertz and D. d. Werra, “Using tabu search techniques for graph coloring,” Computing, vol. 39, no. 4, pp. 345–351, 1987

    1987

  27. [35]

    A variable neighborhood search for graph coloring,

    C. Avanthay, A. Hertz, and N. Zufferey, “A variable neighborhood search for graph coloring,” European Journal of Operational Research , vol. 151, no. 2, pp. 379–388, 2003

    2003

  28. [36]

    A graph coloring heuristic using par- tial solutions and a reactive tabu scheme,

    I. Bl ¨ochliger and N. Zufferey, “A graph coloring heuristic using par- tial solutions and a reactive tabu scheme,” Computers & Operations Research, vol. 35, no. 3, pp. 960–975, 2008

    2008

  29. [37]

    Coloring large graphs based on independent set extraction,

    Q. Wu and J.-K. Hao, “Coloring large graphs based on independent set extraction,” Computers & Operations Research , vol. 39, no. 2, pp. 283–290, 2012

    2012

  30. [38]

    A memetic algorithm for graph coloring,

    Z. L ¨u and J.-K. Hao, “A memetic algorithm for graph coloring,” European Journal of Operational Research, vol. 203, no. 1, pp. 241–250, 2010

    2010

  31. [39]

    Solution to graph coloring using genetic and tabu search procedures,

    R. Marappan and G. Sethumadhavan, “Solution to graph coloring using genetic and tabu search procedures,” Arabian Journal for Science and Engineering, vol. 43, no. 2, pp. 525–542, 2018

    2018

  32. [40]

    Variations on memetic algorithms for graph coloring problems,

    L. Moalic and A. Gondran, “Variations on memetic algorithms for graph coloring problems,” Journal of Heuristics, vol. 24, no. 1, pp. 1–24, 2018

    2018

  33. [41]

    A deep learning guided memetic framework for graph coloring problems,

    O. Goudet, C. Grelier, and J.-K. Hao, “A deep learning guided memetic framework for graph coloring problems,” Knowledge-Based Systems, p. 109986, 2022

    2022

  34. [42]

    A sat approach to branchwidth,

    N. Lodha, S. Ordyniak, and S. Szeider, “A sat approach to branchwidth,” ACM Transactions on Computational Logic (TOCL) , vol. 20, no. 3, pp. 1–24, 2019

    2019

  35. [43]

    Circuit minimization with qbf-based exact synthesis,

    F.-X. Reichl, F. Slivovsky, and S. Szeider, “Circuit minimization with qbf-based exact synthesis,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 4, 2023, pp. 4087–4094

    2023

  36. [44]

    Predicting learnt clauses quality in modern sat solvers,

    G. Audemard and L. Simon, “Predicting learnt clauses quality in modern sat solvers,” in Twenty-first international joint conference on artificial intelligence. Citeseer, 2009

    2009

  37. [45]

    Cadical, kissat, paracooba, plingeling and treengeling entering the sat competition 2020,

    A. Fleury and M. Heisinger, “Cadical, kissat, paracooba, plingeling and treengeling entering the sat competition 2020,” SAT COMPETITION , vol. 2020, p. 50, 2020

    2020

  38. [46]

    An iterative greedy algo- rithm with q-learning mechanism for the multiobjective distributed no- idle permutation flowshop scheduling,

    F. Zhao, C. Zhuang, L. Wang, and C. Dong, “An iterative greedy algo- rithm with q-learning mechanism for the multiobjective distributed no- idle permutation flowshop scheduling,” IEEE Transactions on Systems, Man, and Cybernetics: Systems , 2024

    2024

  39. [47]

    An iterated greedy heuristic for mixed no-wait flowshop problems,

    Y . Wang, X. Li, R. Ruiz, and S. Sui, “An iterated greedy heuristic for mixed no-wait flowshop problems,” IEEE Transactions on Cybernetics , vol. 48, no. 5, pp. 1553–1566, 2018

    2018

  40. [48]

    A knowledge-based two-population optimization algorithm for distributed energy-efficient parallel machines scheduling,

    Z. Pan, D. Lei, and L. Wang, “A knowledge-based two-population optimization algorithm for distributed energy-efficient parallel machines scheduling,” IEEE transactions on cybernetics, vol. 52, no. 6, pp. 5051– 5063, 2020

    2020

  41. [49]

    A hyperheuristic with q-learning for the multiobjective energy-efficient distributed blocking flow shop scheduling problem,

    F. Zhao, S. Di, and L. Wang, “A hyperheuristic with q-learning for the multiobjective energy-efficient distributed blocking flow shop scheduling problem,” IEEE Transactions on Cybernetics , vol. 53, no. 5, pp. 3337– 3350, 2022

    2022

  42. [50]

    A dual-mode local search algorithm for solving the minimum dominating set problem,

    E. Zhu, Y . Zhang, S. Wang, D. Strash, and C. Liu, “A dual-mode local search algorithm for solving the minimum dominating set problem,” Knowledge-Based Systems, vol. 298, p. 111950, 2024

    2024

  43. [51]

    A heuristic initialized stochastic memetic algorithm for mdpvrp with interdependent depot operations,

    A. S. Azad, M. Islam, and S. Chakraborty, “A heuristic initialized stochastic memetic algorithm for mdpvrp with interdependent depot operations,” IEEE Transactions on Cybernetics , vol. 47, no. 12, pp. 4302–4315, 2017

    2017

  44. [52]

    A systematic study on meta-heuristic approaches for solving the graph coloring problem,

    T. Mostafaie, F. M. Khiyabani, and N. J. Navimipour, “A systematic study on meta-heuristic approaches for solving the graph coloring problem,” Computers & Operations Research, vol. 120, p. 104850, 2020

    2020

  45. [53]

    A chaotic binary salp swarm algorithm for solving the graph coloring problem,

    Y . Meraihi, A. Ramdane-Cherif, M. Mahseur, and D. Achelia, “A chaotic binary salp swarm algorithm for solving the graph coloring problem,” in Modelling and Implementation of Complex Systems: Proceedings of the 5th International Symposium, MISC 2018, December 16-18, 2018, Lagh...

    2018

  46. [54]

    The improved colourant algorithm: a hybrid algorithm for solving the graph colouring problem,

    A. F. d. Silva, L. G. A. Rodriguez, and J. F. Filho, “The improved colourant algorithm: a hybrid algorithm for solving the graph colouring problem,” International Journal of Bio-Inspired Computation , vol. 16, no. 1, pp. 1–12, 2020

    2020

  47. [55]

    A hybrid modified pso approach to var- based facility location problems with variable capacity in fuzzy random uncertainty,

    S. Wang and J. Watada, “A hybrid modified pso approach to var- based facility location problems with variable capacity in fuzzy random uncertainty,” Information Sciences, vol. 192, pp. 3–18, 2012

    2012

  48. [56]

    Solving graph coloring problem using divide and conquer-based turbulent particle swarm optimization,

    R. Marappan and G. Sethumadhavan, “Solving graph coloring problem using divide and conquer-based turbulent particle swarm optimization,” Arabian Journal for Science and Engineering , pp. 1–18, 2021

    2021

  49. [57]

    Fast solving maximum weight clique problem in massive graphs

    S. Cai and J. Lin, “Fast solving maximum weight clique problem in massive graphs.” in IJCAI, 2016, pp. 568–574

    2016

  50. [58]

    Network structure and minimum degree,

    S. B. Seidman, “Network structure and minimum degree,” Social net- works, vol. 5, no. 3, pp. 269–287, 1983

    1983

  51. [59]

    Ranking spreaders by decomposing complex networks,

    A. Zeng and C.-J. Zhang, “Ranking spreaders by decomposing complex networks,” Physics letters A , vol. 377, no. 14, pp. 1031–1035, 2013

    2013

  52. [60]

    An o (m) algorithm for cores decompo- sition of networks. corr,

    V . Batagelj and M. Zaversnik, “An o (m) algorithm for cores decompo- sition of networks. corr,” arXiv preprint cs.DS/0310049 , vol. 37, 2003

    2003

  53. [61]

    A systematic survey on influential spreaders identification in complex networks with a focus on k-shell based techniques,

    G. Maji, S. Mandal, and S. Sen, “A systematic survey on influential spreaders identification in complex networks with a focus on k-shell based techniques,” Expert Systems with Applications , vol. 161, p. 113681, 2020

    2020

  54. [62]

    Lewis, Guide to graph colouring

    R. Lewis, Guide to graph colouring . Springer, 2021

    2021

  55. [63]

    Cliques, coloring, and satisfiability: Second dimacs implementation challenge, workshop, october 11- 13, 1993,

    D. J. Johnson and M. A. Trick, “Cliques, coloring, and satisfiability: Second dimacs implementation challenge, workshop, october 11- 13, 1993,” 1996. [Online]. Available: https://api.semanticscholar.org/ CorpusID:118207836

    1993

  56. [64]

    Benchmarking for graph clustering and partitioning,

    P. Sanders, C. Schulz, and D. Wagner, “Benchmarking for graph clustering and partitioning,” Encyclopedia of social network analysis and mining Springer , 2014

    2014

  57. [65]

    SNAP Datasets: Stanford large network dataset collection,

    J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data, Jun. 2014

    2014

  58. [66]

    The network data repository with interactive graph analytics and visualization,

    R. A. Rossi and N. K. Ahmed, “The network data repository with interactive graph analytics and visualization,” in AAAI, 2015

    2015

  59. [67]

    Local search with efficient automatic configuration for minimum vertex cover

    C. Luo, H. H. Hoos, S. Cai, Q. Lin, H. Zhang, and D. Zhang, “Local search with efficient automatic configuration for minimum vertex cover.” in IJCAI, 2019, pp. 1297–1304

    2019

  60. [68]

    The use of ranks to avoid the assumption of normality implicit in the analysis of variance,

    M. Friedman, “The use of ranks to avoid the assumption of normality implicit in the analysis of variance,” Journal of the american statistical association, vol. 32, no. 200, pp. 675–701, 1937

    1937

  61. [69]

    Statistical comparisons of classifiers over multiple data sets,

    J. Dem ˇsar, “Statistical comparisons of classifiers over multiple data sets,” The Journal of Machine learning research , vol. 7, pp. 1–30, 2006

    2006

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.