Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

Computer-assisted graph theory: a survey

T0 review · 2 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read A computer enumeration of 20-vertex triangulations settles the last missing case of the Schmeichel-Hakimi conjecture, and a reused database graph improves the independence-ratio bound for triangle-free degree-5 graphs.

desk verdict Useful survey with two modest new results; Section 5.2's unverified plantri computation needs fixing before the claim is fully credible. read the letter →

arxiv 2508.20825 v1 pith:M2TJG2TY submitted 2025-08-28 math.CO cs.DM

Jorik Jooken This is my paper · ORCID
classification math.COcs.DM MSC 05C1005C0705C3505C30
keywords computer-assistedgraphtheorygenerationplanargraphicaldegreesequencesSchmeichel-Hakimiconjectureindependenceratiotriangle-freegraphsdatabasesexhaustiveenumeration
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

This survey argues that computer-assisted graph theory is underused and shows how readily available tools can settle open problems, illustrating the point with two new results obtained by elementary computation. It closes the 1977 Schmeichel-Hakimi conjecture by proving that the degree sequence 73517 (three vertices of degree 7 and seventeen of degree 5) is not realizable by any planar graph; the check runs in minutes by generating all planar triangulations on 20 vertices and deleting one edge. The second result improves the upper bound on the independence ratio i(5) for triangle-free graphs of maximum degree 5 from 6/20 to 8/28, using a 28-vertex graph already stored in a public graph database. The survey's broader message is that exhaustive generation, searchable databases, optimization, SAT, metaheuristics, and machine learning form a coherent toolkit whose results deserve full algorithmic descriptions.

What carries the argument

The load-bearing step for the first result is the reduction of a planar degree-sequence question to the exhaustive enumeration of planar triangulations: a planar graph with n vertices and degree sum 6n−14 must sit inside a triangulation as a single-edge deletion. The actual enumeration is carried out by a publicly available generator that produces every planar triangulation on 20 vertices up to isomorphism; deleting one edge in all possible ways and checking the resulting degree sequences is then a short computation, not a proof requiring new theory. For the second result, the machinery is a searchable database of graphs with stored invariants; querying for triangle-free graphs of maximum de

What would settle it

Run an independent generation of all planar triangulations on 20 vertices (or an independent SAT or integer-programming encoding of the existence of a planar graph with degree sequence 73517) and find a graph with that degree sequence, or find a missed triangulation whose single-edge deletion matches it; either would falsify the completion of the conjecture. For the i(5) claim, re-checking the cited 28-vertex graph for triangle-freeness, maximum degree 5, and independence number 8 would settle the witness.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central new findings are two. First, the last open case of the Schmeichel-Hakimi conjecture is settled: the degree sequence 73517 is not planar graphical. Because its degree sum is 106 = 6·20 − 14, any planar realization would be obtainable by deleting one edge from a planar triangulation on 20 vertices; exhaustively generating those triangulations, deleting each edge, and comparing degree sequences finds none. Second, for the independence ratio i(5), defined as the infimum of α(G)/n over triangle-free graphs with maximum degree at most 5, the survey records the new upper bound i(5) ≤ 8/28, witnessed by a 28-vertex triangle-free graph of maximum degree 5 with in

Load-bearing premise

The nonexistence claim for 73517 rests on the unverified assumption that the generator exhaustively produced every planar triangulation on 20 vertices and that the subsequent edge-deletion and degree-sequence checks were implemented without error.

Editorial extensions

If this is right

  • If the 73517 check is correct, the Schmeichel-Hakimi conjecture is true and the classification of planar graphical 2-sequences is complete: the exceptions are exactly 4521, 51131, 5533, 71515, 6^{n−7}47, 51331, 71517, and 73517.
  • The best known upper bound for i(5) tightens from 0.3 to 8/28 ≈ 0.2857, so the limiting independence ratio of triangle-free graphs with maximum degree 5, if it exists, lies in the narrower interval [593/2210, 8/28].
  • The reuse of a database graph shows that a graph stored for one problem can directly improve a bound in an unrelated problem, supporting the survey's case for building and searching graph databases.
  • The survey's enumerative template—from a property to a graph class to an exhaustive census to an invariant check—can be applied to other degree-sequence realizability questions without developing new algorithms.
  • The survey consolidates the toolbox of computer-assisted graph theory, making nonexistence proofs and extremal examples accessible to researchers who would not otherwise implement generation, optimization, or SAT machinery from scratch.

Reading between the lines

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

  • An independent re-implementation of the triangulation enumeration, with published output counts or a formal certificate, would eliminate the main residual risk in the 73517 proof; the survey reports no such independent verification.
  • The same edge-deletion reduction can be pushed to k-sequences: any planar graphical sequence with degree sum 6n−12−2k corresponds to deleting k edges from a triangulation, so small values of k are computationally approachable and could reveal further exceptions among low-irregularity sequences.
  • The i(5) bound could be sharpened by mining larger graph censuses for triangle-free maximum-degree-5 graphs with α/n < 8/28, or by targeting a matching lower bound through density methods; neither is attempted in the paper, but the infrastructure is already in place.
  • The survey's own example suggests that printing only the final graph-theoretic result without the algorithm is a real cost to the field; documenting the computational workflow would let others reproduce and reuse it.
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

2 major / 4 minor

Summary. The manuscript is a broad survey of computer-assisted graph theory, covering exhaustive graph generation, graph databases, and algorithmic paradigms such as MILP, semidefinite programming/flag algebras, dynamic programming, SAT solving, metaheuristics, and machine learning. It closes with two small new results: an improved upper bound ip(5) <= 8/28 for the independence ratio of triangle-free graphs of maximum degree 5, obtained by exhibiting a graph from the House of Graphs database (entry 6540), and a proof that the degree sequence 7^3 5^17 is not planar graphical, obtained by exhaustive generation of planar triangulations with plantri. The latter is claimed to settle the last open case of the Schmeichel–Hakimi conjecture.

Significance. If the new computational claims are fully substantiated, the paper is a useful and well-referenced entry point to computer-assisted graph theory, and the Schmeichel–Hakimi result is a notable completion of a 1977 classification. The survey's strengths include its broad coverage, detailed examples from many subareas, and its explicit Section 2.3.2 discussion of correctness standards for non-existence claims. However, the paper's own new Section 5 results currently do not meet those standards: the decisive plantri computation is not reproducible, and the graph used for the ip(5) bound is not described. These issues are local and fixable, so the appropriate outcome is revision rather than rejection.

major comments (2)
  1. [§5.2] The proof that 73517 is not planar graphical rests entirely on an unverified plantri computation. The text gives no plantri version, command-line options, number of triangulations generated, pruning criteria, edge-orbit reduction, or code for the edge-removal/degree-sequence filter. It only states that the computation 'yields the result in a matter of minutes.' Since this is a non-existence claim, the paper's own §2.3.2 requires at least a formal description of the algorithm, comparison with known censuses, and independent implementation checks. At minimum, the authors should report the exact plantri invocation, the count of triangulations considered (e.g., planar triangulations on 20 vertices with minimum degree 5, together with a justification for that restriction), and a reproducible script or log that independently verifies the absence of the degree sequence after edge removal. Witho
  2. [§5.1] The new bound ip(5) <= 8/28 relies on the existence of a triangle-free graph on 28 vertices with maximum degree 5 and independence number 8. The paper only cites House of Graphs entry 6540 and a figure; it does not provide the graph in machine-readable form (e.g., graph6), nor does it state how alpha(G)=8 was verified. Since the graph is external to the manuscript, a reader cannot independently confirm the bound from the text. Please include the graph6 encoding or adjacency list and either a short certificate for the independence number or the output of an independent solver. This is a load-bearing detail for the claimed improvement over the previous upper bound 6/20 = 0.3.
minor comments (4)
  1. [§2.1 / Table 2] For readability, state explicitly that the counts in Table 2 are for 3-connected graphs and that plantri can generate graphs that are not 3-connected. This distinction matters for Section 5.2, where the relevant triangulations are maximal planar graphs.
  2. [§5.2, Theorem 5.1] The notation '6n−747' in the statement of Schmeichel–Hakimi is ambiguous in the text. It should be typeset as 6^{n-7}4^7, matching the shorthand defined earlier.
  3. [References] Reference [75] is listed as 'Springer-Verslag'; this should be 'Springer-Verlag'.
  4. [§5.1 / §5.2] Figures 7 and 8 are informative but would be more useful if each graph's graph6 encoding or House of Graphs identifier appeared in the caption, so that the reader does not need to transcribe the drawing.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: both new results rest on external exhaustive computation and databases, not on the claims themselves.

full rationale

The paper's two new claims are independent of its own derivations. Section 5.1 obtains ip(5) <= 8/28 from House of Graphs entry 6540, an externally hosted graph with checkable invariants; the bound is just the graph's independence ratio and does not presuppose the bound. Section 5.2's proof that 73517 is not planar graphical reduces, via the standard observation that any planar realization has 53 edges and hence a quadrilateral face, to exhaustive generation of 20-vertex planar triangulations by plantri, followed by edge removal and degree-sequence checks. The enumeration and check are supplied by an external, established generator; the logical equivalence is a reduction to a finite computation, not an equation that defines the target. The paper's many self-citations (e.g., [24,49,50,88,102,103,104,105,136,246,247]) are illustrative examples of the surveyed methodology and are not load-bearing for either new result. Section 2.3.2's own warning that non-existence claims require formal correctness arguments, comparison with known censuses, or independent implementations is a relevant reproducibility concern that the paper does not satisfy for the Section 5.2 computation (no scripts, plantri version, or output counts are given); however, missing verification is a correctness risk, not a circularity, since no fitted parameter is relabeled as a prediction and no conclusion is assumed by construction.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The survey itself introduces no free parameters or new entities. The two new results rely on standard graph theory facts and on the correctness of external tools and databases.

assumptions (3)
  • standard math Euler's formula: a maximal planar graph on n vertices has 3n - 6 edges.
    Used in Section 5.2 to argue that a planar graph with 20 vertices and 53 edges is one edge short of a triangulation.
  • domain assumption plantri exhaustively and correctly generates all pairwise non-isomorphic planar triangulations on 20 vertices.
    The non-existence proof of 73517 in Section 5.2 depends on the exhaustiveness of plantri.
  • domain assumption The House of Graphs entry 6540 is a triangle-free graph on 28 vertices with maximum degree 5 and independence number 8.
    The improved i(5) bound in Section 5.1 rests on the correctness of the database record, which is not re-verified in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computer-assisted graph theory: a survey." pith.science (2026). https://pith.science/paper/M2TJG2TY

@misc{pith2026250820825,
  author       = {Pith},
  title        = {Pith review of: Computer-assisted graph theory: a survey},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/M2TJG2TY}},
  note         = {Machine review of arXiv:2508.20825}
}
read the original abstract

Computers and algorithms play an ever-increasing role in obtaining new results in graph theory. In this survey, we present a broad range of techniques used in computer-assisted graph theory, including the exhaustive generation of all pairwise non-isomorphic graphs within a given class, the use of searchable databases containing graphs and invariants as well as other established and emerging algorithmic paradigms. We cover approaches based on mixed integer linear programming, semidefinite programming, dynamic programming, SAT solving, metaheuristics and machine learning. The techniques are illustrated with numerous detailed results covering several important subareas of graph theory such as extremal graph theory, graph coloring, structural graph theory, spectral graph theory, regular graphs, topological graph theory, special sets in graphs, algebraic graph theory and chemical graph theory. We also present some smaller new results that demonstrate how readily a computer-assisted graph theory approach can be applied once the appropriate tools have been developed.

Figures

Figures reproduced from arXiv: 2508.20825 by the authors.

Figure 1
Figure 1. The graphs C3, C4, C5, K4 and K1,3 (the last one is also known as the claw graph). Other graph generators in the nauty package include gentreeg (for generating all trees on n vertices, where bounds for the diameter and an upper bound for the maximum degree can also be specified), genktreeg (for generating all k-trees on n vertices, i.e., the maximal graphs with treewidth k [190]), genquarticg (for generating 4-regul… view at source ↗
Figure 2
Figure 2. A part of the recursion tree showing the first and the second situation that may lead [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. A part of the recursion tree showing the third situation that may lead to isomorphic [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: A triangle-free graph on 20 vertices with exactly p 20 5 q 5 “ 1024 cycles of length 5. G is triangle-free and |V pGq| “ nu, let πC5 pK3q “ limnÑ8 exC5 pn,K3q p n 5q and let H denote the set of all triangle-free graphs on at most 5 vertices. The crucial inequality deri…
Figure 5
Figure 5. Figure 5: A repeatable graph with respect to δ “ 4 and χ “ 3 and a gluing-like operation. The different vertex styles show a proper 3-coloring. It was shown in [50] that if G is a repeatable graph with respect to δ and χ induced by neighborhoods N0, N1, . . . , Nd, then cδ,χ ě d…
Figure 6
Figure 6. Figure 6: A graph G on 30 vertices for which πpGq ` Bt 2D 3 u « 0.4. Wagner [238] showed that this intuition is indeed correct: by taking a path on 13 vertices and appending 190 pendant vertices to the vertex at distance 4 from one end on this path, one obtains a counterexample …
Figure 7
Figure 7. Figure 7: Two graphs showing that ip3q ď 5 14 « 0.357 (left) and ip4q ď 4 13 « 0.307 (right). The circles indicate a maximum independent set. 3We emphasize the importance of properly citing such tools when they are used. 29 [PITH_FULL_IMAGE:figures/full_fig_p029_7.png]
Figure 8
Figure 8. Figure 8: Two graphs showing that ip5q ď 6 20 “ 0.3 (left) and ip5q ď 8 28 « 0.286 (right). The circles indicate a maximum independent set. 5.2 Planar graphical degree sequences A sequence of n integers d “ pd1, d2, . . . , dnq is called graphical if there exists a graph having …

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. New small regular graphs of given girth: the cage problem and beyond

    math.CO 2025-11 conditional novelty 7.0 of 10

    New computational constructions give new record upper bounds for n(k,g) in 11 cases, including n(4,10) ≤ 320, n(3,16) ≤ 936, and n(3,17) ≤ 2048.

Reference graph

Works this paper leans on

250 extracted references · 73 canonical work pages · cited by 1 Pith paper

  1. [1]

    S. N. Afzaly. Generation of graph classes with efficient isomorph rejection.PhD thesis, 2016

    2016

  2. [2]

    R. E. Aldred, B. D. McKay, and N. C. Wormald. Small hypohamiltonian graphs.Journal of Combinatorial Mathematics and Combinatorial Computing, 23:143–152, 1997

    1997

  3. [3]

    Althöfer, J

    I. Althöfer, J. K. Haugland, K. Scherer, F. Schneider, and N. Van Cleemput. Alternating plane graphs. Ars Mathematica Contemporanea, 8(2):337–363, 2015

    2015

  4. [4]

    Anders and P

    M. Anders and P. Schweitzer. Engineering a fast probabilistic isomorphism test. In2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), pages 73–84. SIAM, 2021

    2021

  5. [5]

    Anders and P

    M. Anders and P. Schweitzer. Parallel Computation of Combinatorial Symmetries. In P. Mutzel, R. Pagh, and G. Herman, editors,29th Annual European Symposium on Algorithms (ESA 2021), volume 204 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

    2021

  6. [6]

    Anders and P

    M. Anders and P. Schweitzer. Search Problems in Trees with Symmetries: Near Optimal Traversal Strategies for Individualization-Refinement Algorithms. In N. Bansal, E. Merelli, and J. Worrell, editors,48th International Colloquium on Automata, Languages, and Pro- gramming (ICALP 2021), volume 198 ofLeibniz International Proceedings in Informatics (LIPIcs),...

    2021

  7. [7]

    $R(5,5)\le 46$

    V. Angeltveit and B. D. McKay.Rp5, 5qď 46. arXiv preprint arXiv:2409.15709, 2024. 31

    work page Pith review arXiv 2024

  8. [8]

    Aouchiche, F

    M. Aouchiche, F. K. Bell, D. Cvetković, P. Hansen, P. Rowlinson, S. K. Simić, and D. Stevanović. Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph.European Journal of Operational Research, 191(3):661–676, 2008

    2008

Show all 250 references
  1. [9]

    Aouchiche, J.-M

    M. Aouchiche, J.-M. Bonnefoy, A. Fidahoussen, G. Caporossi, P. Hansen, L. Hiesse, J. Lacheré, and A. Monhait. Variable neighborhood search for extremal graphs 14: the AutoGraphiX 2 system. InGlobal optimization: from theory to implementation, pages 281–310. Springer, 2006

    2006

  2. [10]

    Aouchiche and P

    M. Aouchiche and P. Hansen. Proximity, remoteness and distance eigenvalues of a graph. Discrete Applied Mathematics, 213:17–25, 2016

    2016

  3. [11]

    Appel and W

    K. Appel and W. Haken. Every planar map is four colorable. Part I: Discharging.Illinois Journal of Mathematics, 21(3):429–490, 1977

    1977

  4. [12]

    Appel and W

    K. Appel and W. Haken. Every planar map is four colorable, volume 98. American Mathematical Society, 1989

    1989

  5. [13]

    Appel, W

    K. Appel, W. Haken, and J. Koch. Every planar map is four colorable. Part II: Reducibility. Illinois Journal of Mathematics, 21(3):491–567, 1977

    1977

  6. [14]

    Babai, D

    L. Babai, D. Y. Grigoryev, and D. M. Mount. Isomorphism of graphs with bounded eigenvalue multiplicity. In Proceedings of the fourteenth annual ACM Symposium on Theory of Computing, pages 310–324, 1982

    1982

  7. [15]

    Balogh, P

    J. Balogh, P. Hu, B. Lidický, F. Pfender, J. Volec, and M. Young. Rainbow triangles in three-colored graphs. Journal of Combinatorial Theory, Series B, 126:83–113, 2017

    2017

  8. [16]

    Bar-Noy, T

    A. Bar-Noy, T. Böhnlein, D. Peleg, Y. Ran, and D. Rawitz. Sparse graphic degree sequences have planar realizations. In49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), pages 18:1–18:17. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2024

    2024

  9. [17]

    Barabási

    A.-L. Barabási. Network science. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 371(1987):20120375, 2013

    1987

  10. [18]

    Belhaiza, N

    S. Belhaiza, N. M. M. de Abreu, P. Hansen, and C. S. Oliveira. Variable neighborhood search for extremal graphs. XI. Bounds on algebraic connectivity. InGraph Theory and Combinatorial Optimization, pages 1–16. Springer, 2005

    2005

  11. [19]

    R. Bellman. The theory of dynamic programming.Bulletin of the American Mathematical Society, 60(6):503–515, 1954

    1954

  12. [20]

    Berčič and J

    K. Berčič and J. Vidali. DiscreteZOO: A Fingerprint Database of Discrete Ob- jects. Mathematics in Computer Science, 14(3):559–575, 2020. Available at https: //discretezoo.xyz/

    2020

  13. [21]

    Bertsimas and J

    D. Bertsimas and J. N. Tsitsiklis.Introduction to Linear Optimization. Athena Scientific, 1997. 32

    1997

  14. [22]

    A. Biere. CaDiCaL, Lingeling, Plingeling, Treengeling and YalSAT Entering the SAT competition 2018. Proceedings of SAT Competition - Solver and Benchmark Descriptions, pages 13–14, 2018

    2018

  15. [23]

    Biere, K

    A. Biere, K. Fazekas, M. Fleury, and M. Heisinger. CaDiCaL, Kissat, Paracooba, Plingeling and Treengeling Entering the SAT competition 2020.Proceedings of SAT Competition - Solver and Benchmark Descriptions, pages 51–53, 2020

    2020

  16. [24]

    Birkinshaw, P

    A. Birkinshaw, P. W. Fowler, J. Goedgebeur, and J. Jooken. On graphs isomorphic with their conduction graph.MATCH Commun. Math. Comput. Chem., 93:379–413, 2025

    2025

  17. [25]

    J. R. Blair and B. Peyton. An introduction to chordal graphs and clique trees. InGraph Theory and Sparse Matrix Computation, pages 1–29. Springer, 1993

    1993

  18. [26]

    H. L. Bodlaender. Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. Journal of Algorithms, 11(4):631–643, 1990

    1990

  19. [27]

    Bousquet, Q

    N. Bousquet, Q. Deschamps, L. de Meyer, and T. Pierron. Square coloring planar graphs with automatic discharging.SIAM Journal on Discrete Mathematics, 38(1):504–528, 2024

    2024

  20. [28]

    Brakensiek, M

    J. Brakensiek, M. J. H. Heule, J. Mackey, and D. Narváez. The resolution of Keller’s conjecture. Journal of Automated Reasoning, 66(3):277–300, 2022

    2022

  21. [29]

    Brandt, G

    S. Brandt, G. Brinkmann, and T. Harmuth. All Ramsey numbersRpK3, Gq for connected graphs of order 9.Electronic Journal of Combinatorics, 5:R7, 1998

    1998

  22. [30]

    Brandt, G

    S. Brandt, G. Brinkmann, and T. Harmuth. The generation of maximal triangle-free graphs. Graphs and Combinatorics, 16:149–157, 2000

    2000

  23. [31]

    Brinkmann

    G. Brinkmann. Fast generation of cubic graphs.Journal of Graph Theory, 23(2):139–149, 1996

    1996

  24. [32]

    Brinkmann

    G. Brinkmann. Isomorphism rejection in structure generation programs.Discrete Mathe- matical Chemistry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 51:25–38, 2000

    2000

  25. [33]

    Brinkmann

    G. Brinkmann. Generating maps on oriented surfaces using the homomorphism principle. Discrete & Computational Geometry, pages 1–11, 2025

    2025

  26. [34]

    Brinkmann, K

    G. Brinkmann, K. Coolsaet, J. Goedgebeur, and H. Mélot. House of Graphs: a database of interesting graphs.Discrete Applied Mathematics, 161(1-2):311–314, 2013. Available at https://houseofgraphs.org/

    2013

  27. [35]

    Brinkmann and A

    G. Brinkmann and A. W. Dress. A constructive enumeration of fullerenes.Journal of Algorithms, 23(2):345–358, 1997

    1997

  28. [36]

    Brinkmann, O

    G. Brinkmann, O. D. Friedrichs, S. Lisken, A. Peeters, and N. Van Cleemput. CaGe – a virtual environment for studying some special classes of plane graphs – an update. MATCH Commun. Math. Comput. Chem, 63(3):533–552, 2010

    2010

  29. [37]

    Brinkmann, J

    G. Brinkmann, J. Goedgebeur, J. Hägglund, and K. Markström. Generation and properties of snarks. Journal of Combinatorial Theory, Series B, 103(4):468–488, 2013. 33

    2013

  30. [38]

    Brinkmann, J

    G. Brinkmann, J. Goedgebeur, and B. D. McKay. Generation of cubic graphs.Discrete Mathematics & Theoretical Computer Science, 13(2), 2011

    2011

  31. [39]

    Brinkmann, J

    G. Brinkmann, J. Goedgebeur, and B. D. McKay. The generation of fullerenes.Journal of Chemical Information and Modeling, 52(11):2910–2918, 2012

    2012

  32. [40]

    Brinkmann, J

    G. Brinkmann, J. Goedgebeur, and B. D. McKay. The minimality of the Georges–Kelmans graph. Mathematics of Computation, 91(335):1483–1500, 2022

    2022

  33. [41]

    Brinkmann, J

    G. Brinkmann, J. Goedgebeur, and J. C. Schlage-Puchta. Ramsey numbersRpK3, Gq for graphs of order 10.Electronic Journal of Combinatorics, 19:P36, 2012

    2012

  34. [42]

    Brinkmann, S

    G. Brinkmann, S. Greenberg, C. Greenhill, B. D. McKay, R. Thomas, and P. Wollan. Generation of simple quadrangulations of the sphere.Discrete Mathematics, 305(1-3):33–54, 2005

    2005

  35. [43]

    Brinkmann and B

    G. Brinkmann and B. D. McKay. Construction of planar triangulations with minimum degree 5. Discrete Mathematics, 301(2-3):147–163, 2005

    2005

  36. [44]

    Brinkmann and B

    G. Brinkmann and B. D. McKay. Fast generation of planar graphs.MATCH Commun. Math. Comput. Chem., pages 323–357, 2007

    2007

  37. [45]

    Brinkmann, B

    G. Brinkmann, B. D. McKay, and C. Saager. The smallest cubic graphs of girth nine. Combinatorics, Probability and Computing, 4(4):317–329, 1995

    1995

  38. [46]

    Brinkmann and N

    G. Brinkmann and N. Van Cleemput. Classification and generation of nanocones.Discrete Applied Mathematics, 159(15):1528–1539, 2011

    2011

  39. [47]

    A. E. Brouwer. Dataset of strongly regular graphs. URL:https://aeb.win.tue.nl/ graphs/srg/srgtab.html (accessed 2025-08-08)

    2025

  40. [48]

    A. E. Brouwer and H. Van Maldeghem.Strongly regular graphs, volume 182. Cambridge University Press, 2022

    2022

  41. [49]

    Cambie and J

    S. Cambie and J. Jooken. Counterexamples to conjectures on the occupancy fraction of graphs. Mathematics of Computation, 2025. To appear

    2025

  42. [50]

    Cambie and J

    S. Cambie and J. Jooken. Sharp results for the Erdős, Pach, Pollack and Tuza problem. arXiv preprint arXiv:2502.08626, 2025

    2025 arXiv

  43. [51]

    Caporossi

    G. Caporossi. Variable neighborhood search for extremal vertices: The AutoGraphiX-III system. Computers & Operations Research, 78:431–438, 2017

    2017

  44. [52]

    Caporossi and P

    G. Caporossi and P. Hansen. Variable neighborhood search for extremal graphs: 1 The AutoGraphiX system. Discrete Mathematics, 212:29–44, 2000

    2000

  45. [53]

    Cattell, F

    K. Cattell, F. Ruskey, J. Sawada, M. Serra, and C. R. Miers. Fast algorithms to generate necklaces, unlabeled necklaces, and irreducible polynomials over GF(2). Journal of Algorithms, 37(2):267–282, 2000

    2000

  46. [54]

    Chudnovsky, N

    M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem. Annals of Mathematics, pages 51–229, 2006. 34

    2006

  47. [55]

    V. Chvátal. Linear programming. Macmillan, 1983

    1983

  48. [56]

    Magma Computational Algebra System

    Computational Algebra Group, University of Sydney. Magma Computational Algebra System. URL: https://magma.maths.usyd.edu.au/magma/ (accessed 2025-08-08)

    2025

  49. [57]

    M. Conder. Combinatorial data. URL:https://www.math.auckland.ac.nz/~conder/ (accessed 2025-08-08)

    2025

  50. [58]

    Conder and P

    M. Conder and P. Dobcsányi. Trivalent symmetric graphs on up to 768 vertices.Journal of Combinatorial Mathematics and Combinatorial Computing, 40:41–64, 2002

    2002

  51. [59]

    Conder, A

    M. Conder, A. Malnič, D. Marušič, and P. Potočnik. A census of semisymmetric cubic graphs on up to 768 vertices.Journal of Algebraic Combinatorics, 23:255–294, 2006

    2006

  52. [60]

    Conder and P

    M. Conder and P. Potočnik. Edge-transitive cubic graphs: Cataloguing and Enumeration. arXiv preprint arXiv:2502.02250, 2025

    2025 arXiv

  53. [61]

    Thestronglyregular p45, 12, 3, 3qgraphs

    K.Coolsaet, J.Degraer, andE.Spence. Thestronglyregular p45, 12, 3, 3qgraphs. Electronic Journal of Combinatorics, 13:R32, 2006

    2006

  54. [62]

    Coolsaet, S

    K. Coolsaet, S. D’hondt, and J. Goedgebeur. House of Graphs 2.0: A database of interesting graphs and more.Discrete Appl. Math., 325:97–107, 2023. Available athttps: //houseofgraphs.org/

    2023

  55. [63]

    Coolsaet, P

    K. Coolsaet, P. W. Fowler, and J. Goedgebeur. Generation and properties of of nut graphs. MATCH Commun. Math. Comput. Chem., pages 423–444, 2018

    2018

  56. [64]

    Corrádi and S

    K. Corrádi and S. Szabó. A combinatorial approach for Keller’s conjecture.Periodica Mathematica Hungarica, 21(2):95–100, 1990

    1990

  57. [65]

    D. W. Cranston and D. B. West. An introduction to the discharging method via graph coloring. Discrete Mathematics, 340(4):766–793, 2017

    2017

  58. [66]

    Cruz-Filipe, M

    L. Cruz-Filipe, M. J. H. Heule, W. A. Hunt Jr, M. Kaufmann, and P. Schneider-Kamp. Efficient certified RAT verification. InInternational Conference on Automated Deduction, pages 220–236. Springer, 2017

    2017

  59. [67]

    Cummings, D

    J. Cummings, D. Král’, F. Pfender, K. Sperfeld, A. Treglown, and M. Young. Monochro- matic triangles in three-coloured graphs.Journal of Combinatorial Theory, Series B, 103(4):489–503, 2013

    2013

  60. [68]

    Czabarka, I

    É. Czabarka, I. Singgih, and L. A. Székely. Counterexamples to a conjecture of Erdős, Pach, Pollack and Tuza.Journal of Combinatorial Theory, Series B, 151:38–45, 2021

    2021

  61. [69]

    G. B. Dantzig. Linear programming and extensions. 2016

    2016

  62. [70]

    P. T. Darga, M. H. Liffiton, K. A. Sakallah, and I. L. Markov. Exploiting structure in symmetry detection for CNF. In Proceedings of the 41st Annual Design Automation Conference, pages 530–534, 2004

    2004

  63. [71]

    P. T. Darga, K. A. Sakallah, and I. L. Markov. Faster symmetry discovery using sparsity of symmetries. InProceedings of the 45th annual Design Automation Conference, pages 149–154, 2008. 35

    2008

  64. [72]

    S. Das, H. Huang, J. Ma, H. Naves, and B. Sudakov. A problem of Erdős on the minimum number of k-cliques. Journal of Combinatorial Theory, Series B, 103(3):344–373, 2013

    2013

  65. [73]

    De Silva, K

    J. De Silva, K. Heysse, A. Kapilow, A. Schenfisch, and M. Young. Turán numbers of vertex-disjoint cliques inr-partite graphs. Discrete Mathematics, 341(2):492–496, 2018

    2018

  66. [74]

    Devillez, P

    G. Devillez, P. Hauweele, and H. Mélot. PHOEG helps to obtain extremal graphs. InOper- ations Research Proceedings 2018: Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), Brussels, Belgium, September 12-14, 2018, page 251. ...

    2018

  67. [75]

    Diestel.Graph Theory

    R. Diestel.Graph Theory. Springer-Verslag, 6th edition, 2025. Electronic edition available at http://diestel-graph-theory.com/

    2025

  68. [76]

    M. J. Dinneen and P. R. Hafner. New results for the degree/diameter problem.Networks, 24(7):359–367, 1994

    1994

  69. [77]

    T. Ekim, M. Shalom, and M. A. Yirik. Generation of weighted trees, block trees and block graphs. arXiv preprint arXiv:2401.09764, 2024

    2024 arXiv

  70. [78]

    P. Erdős. Some remarks on number theory.Riveon Lematematika, 9:45–48, 1955

    1955

  71. [79]

    P. Erdős. On some problems in graph theory, combinatorial analysis and combinato- rial number theory. InGraph Theory and Combinatorics, Proc. Conf. Hon. P. Erdős, Cambridge, 1983, pages 1–17, 1984

    1983

  72. [80]

    Erdős and T

    P. Erdős and T. Gallai. Graphs with prescribed degrees of vertices.Matematikai Lapok, 11:264–274, 1960

    1960

  73. [81]

    Erdős, J

    P. Erdős, J. Pach, R. Pollack, and Z. Tuza. Radius, diameter, and minimum degree. Journal of Combinatorial Theory, Series B, 47(1):73–79, 1989

    1989

  74. [82]

    G. Exoo. A family of graphs and the degree/diameter problem.Journal of Graph Theory, 37(2):118–124, 2001

    2001

  75. [83]

    G. Exoo. Voltage graphs, group presentations and cages.Electronic Journal of Combina- torics, 11(1):N2, 2004

    2004

  76. [84]

    G. Exoo. On the Ramsey numberRp4, 6q. Electronic Journal of Combinatorics, 19:P66, 2012

    2012

  77. [85]

    Exoo and R

    G. Exoo and R. Jajcay. Dynamic cage survey. Electronic Journal of Combinatorics, DS16–Jul, 2012

    2012

  78. [86]

    G. Exoo, T. Kolokolnikov, J. Janssen, and T. Salamon. Attainable bounds for algebraic connectivityandmaximallyconnectedregulargraphs. Journal of Graph Theory, 107(3):522– 549, 2024

    2024

  79. [87]

    G. Exoo, B. D. McKay, W. Myrvold, and J. Nadon. Computational determination of p3, 11q andp4, 7q cages. Journal of Discrete Algorithms, 9(2):166–169, 2011. 36

    2011

  80. [88]

    L. C. Eze, R. Jajcay, and J. Jooken. Onpk, gq-graphs withoutpg` 1q-cycles. Applied Mathematics and Computation, 508:129645, 2026

    2026

  81. [89]

    Fabrici, T

    I. Fabrici, T. Madaras, M. Timková, N. Van Cleemput, and C. T. Zamfirescu. Non- hamiltonian graphs in which every edge-contracted subgraph is hamiltonian.Applied Mathematics and Computation, 392:125714, 2021

    2021

  82. [90]

    Fajtlowicz

    S. Fajtlowicz. On conjectures of Graffiti. InAnnals of Discrete Mathematics, volume 38, pages 113–118. Elsevier, 1988

    1988

  83. [91]

    Fulkerson’sconjectureandcircuitcovers

    G.FanandA.Raspaud. Fulkerson’sconjectureandcircuitcovers. Journal of Combinatorial Theory, Series B, 61(1):133–138, 1994

    1994

  84. [92]

    S. Fanelli. An unresolved conjecture on nonmaximal planar graphical sequences.Discrete Mathematics, 36(1):109–112, 1981

    1981

  85. [93]

    I. A. Faradžev. Generation of nonisomorphic graphs with a given degree sequence. Algorithmic Studies in Combinatorics, pages 11–19, 1978

    1978

  86. [94]

    Franchetti, S

    F. Franchetti, S. Kral, J. Lorenz, and C. W. Ueberhuber. Efficient utilization of SIMD extensions. Proceedings of the IEEE, 93(2):409–425, 2005

    2005

  87. [95]

    Blockingandanti-blockingpairsofpolyhedra

    D.R.Fulkerson. Blockingandanti-blockingpairsofpolyhedra. Mathematical Programming, 1:168–194, 1971

    1971

  88. [96]

    García-Marco and K

    I. García-Marco and K. Knauer. Coloring minimal Cayley graphs.European Journal of Combinatorics, 125:104108, 2025

    2025

  89. [97]

    F. W. Glover. Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5):533–549, 1986

    1986

  90. [98]

    F. W. Glover. Tabu search-part I.ORSA Journal on computing, 1(3):190–206, 1989

    1989

  91. [99]

    F. W. Glover and G. A. Kochenberger.Handbook of metaheuristics, volume 57. Springer Science & Business Media, 2003

    2003

  92. [100]

    Goddard, M

    W. Goddard, M. A. Henning, and O. R. Oellermann. Bipartite Ramsey numbers and Zarankiewicz numbers. Discrete Mathematics, 219(1-3):85–95, 2000

    2000

  93. [101]

    Goedgebeur

    J. Goedgebeur. On minimal triangle-free 6-chromatic graphs.Journal of Graph Theory, 93(1):34–48, 2020

    2020

  94. [102]

    Goedgebeur and J

    J. Goedgebeur and J. Jooken. Exhaustive generation of edge-girth-regular graphs.Experi- mental Mathematics, pages 1–13, 2025

    2025

  95. [103]

    Goedgebeur, J

    J. Goedgebeur, J. Jooken, O.-H. S. Lo, B. Seamone, and C. T. Zamfirescu. Few hamiltonian cyclesingraphswithoneortwovertexdegrees. Mathematics of Computation, 93(350):3059– 3082, 2024. 37

    2024

  96. [104]

    Goedgebeur, J

    J. Goedgebeur, J. Jooken, K. Okrasa, P. Rzążewski, and O. Schaudt. Minimal Obstructions to C5-Coloring in Hereditary Graph Classes. In R. Královič and A. Kučera, editors,49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), volume 306 ofLeib...

    2024

  97. [105]

    Goedgebeur, J

    J. Goedgebeur, J. Jooken, and T. Van den Eede. Computational methods for finding bi-regular cages. arXiv preprint arXiv:2411.17351, 2024

    2024 arXiv

  98. [106]

    Goedgebeur and B

    J. Goedgebeur and B. D. McKay. Recursive generation of IPR fullerenes.Journal of Mathematical Chemistry, 53(8):1702–1724, 2015

    2015

  99. [107]

    Goedgebeur, B

    J. Goedgebeur, B. Meersman, and C. T. Zamfirescu. Graphs with few hamiltonian cycles. Mathematics of Computation, 89(322):965–991, 2020

    2020

  100. [108]

    Goedgebeur, A

    J. Goedgebeur, A. Neyt, and C. T. Zamfirescu. Structural and computational results on platypus graphs. Applied Mathematics and Computation, 386:125491, 2020

    2020

  101. [109]

    Goedgebeur, K

    J. Goedgebeur, K. Noguchi, J. Renders, and C. T. Zamfirescu. HIST-critical graphs and Malkevitch’s conjecture.arXiv preprint arXiv:2401.04554, 2024

    2024 arXiv

  102. [110]

    Goedgebeur and S

    J. Goedgebeur and S. P. Radziszowski. New computational upper bounds for Ramsey numbers Rp3, kq. Electronic Journal of Combinatorics, 20:P30, 2013

    2013

  103. [111]

    Goedgebeur and J

    J. Goedgebeur and J. Renders. Generation of cycle permutation graphs and permutation snarks. InInternational Conference on Current Trends in Theory and Practice of Computer Science, pages 333–346. Springer, 2025

    2025

  104. [112]

    Goedgebeur, J

    J. Goedgebeur, J. Renders, G. Wiener, and C. T. Zamfirescu.K2-hamiltonian graphs: II. Journal of Graph Theory, 105(4):580–611, 2024

    2024

  105. [113]

    Goedgebeur, J

    J. Goedgebeur, J. Renders, and C. T. Zamfirescu. Generation and new infinite families of K2-hypohamiltonian graphs. Discrete Mathematics, 347(7):113981, 2024

    2024

  106. [114]

    Goedgebeur and O

    J. Goedgebeur and O. Schaudt. Exhaustive generation ofk-critical H-free graphs.Journal of Graph Theory, 87(2):188–207, 2018

    2018

  107. [115]

    Goedgebeur and C

    J. Goedgebeur and C. T. Zamfirescu. Improved bounds for hypohamiltonian graphs.Ars Mathematica Contemporanea, 13:235–257, 2017

    2017

  108. [116]

    Gonthier

    G. Gonthier. The four colour theorem: Engineering of a formal proof. InAsian Symposium on Computer Mathematics, pages 333–333. Springer, 2007

    2007

  109. [117]

    Greenhill

    C. Greenhill. Generating graphs randomly.Surveys in Combinatorics, pages 133–186, 2021

    2021

  110. [118]

    J. Grochow. New applications of the polynomial method: the cap set conjecture and beyond. Bulletin of the American Mathematical Society, 56(1):29–64, 2019

    2019

  111. [119]

    Grund, A

    R. Grund, A. Kerber, and R. Laue. MOLGEN - ein Computeralgebrasystem für die Konstruktion molekularer Graphen.MATCH Commun. Math. Comput. Chem., 27:87–131, 1992. 38

    1992

  112. [120]

    A. Grzesik. On the maximum number of five-cycles in a triangle-free graph.Journal of Combinatorial Theory, Series B, 102(5):1061–1066, 2012

    2012

  113. [121]

    Version 11.0

    Gurobi Optimization, LLC.Gurobi Optimizer Reference Manual, 2024. Version 11.0

    2024

  114. [122]

    I. Gutman. Geometric approach to degree-based topological indices: Sombor indices. MATCH Commun. Math. Comput. Chem, 86(1):11–16, 2021

    2021

  115. [123]

    W. H. Haemers and E. Spence. The pseudo-geometric graphs for generalized quadrangles of orderp3, tq. European Journal of Combinatorics, 22(6):839–845, 2001

    2001

  116. [124]

    W. H. Haemers and E. Spence. Enumeration of cospectral graphs.European Journal of Combinatorics, 25(2):199–211, 2004

    2004

  117. [125]

    Hansen and G

    P. Hansen and G. Caporossi. AutoGraphiX: An Automated System for Finding Conjectures in Graph Theory.Electronic Notes in Discrete Mathematics, 5:158–161, 2000

    2000

  118. [126]

    Hansen and H

    P. Hansen and H. Mélot. Variable neighborhood search for extremal graphs. 9. Bounding the irregularity of a graph.DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 69:253, 2005

    2005

  119. [127]

    Hatami, J

    H. Hatami, J. Hladký, D. Král’, S. Norine, and A. Razborov. On the number of pentagons in triangle-free graphs.Journal of Combinatorial Theory, Series A, 120(3):722–732, 2013

    2013

  120. [128]

    C. T. Hoàng, B. Moore, D. Recoskie, J. Sawada, and M. Vatshelle. Constructions of k-critical P5-free graphs. Discrete Applied Mathematics, 182:91–98, 2015

    2015

  121. [129]

    Holt and G

    D. Holt and G. Royle. A census of small transitive groups and vertex-transitive graphs. Journal of Symbolic Computation, 101:51–60, 2020

    2020

  122. [130]

    Overview of graph generators and censuses

    House of Graphs. Overview of graph generators and censuses. URL: https:// houseofgraphs.org/meta-directory (accessed 2025-08-08)

    2025

  123. [131]

    A. Huck. Reducible configurations for the cycle double cover conjecture.Discrete Applied Mathematics, 99(1-3):71–90, 2000

    2000

  124. [132]

    IBM ILOG CPLEX Optimization Studio, 2023

    IBM Corporation. IBM ILOG CPLEX Optimization Studio, 2023. Version 22.1

    2023

  125. [133]

    Ihringer

    F. Ihringer. Dataset of strongly regular graphs. URL:https://math.ihringer.org/ srgs.php (accessed 2025-08-08)

    2025

  126. [134]

    R. Isaacs. Infinite families of nontrivial trivalent graphs which are not Tait colorable.The American Mathematical Monthly, 82(3):221–239, 1975

    1975

  127. [135]

    F. Jaeger. Nowhere-zero flow problems. InSelected topics in graph theory, 3, pages 71–95. Academic Press, San Diego, CA, 1988

    1988

  128. [136]

    Jajcay, J

    R. Jajcay, J. Jooken, and I. Porupsánszki. On vertex-girth-regular graphs: (Non-)existence, bounds and enumeration.arXiv preprint arXiv:2408.14557, 2024

    2024 arXiv

  129. [137]

    Á. A. Jones, F. Protti, and R. R. Del-Vecchio. Cograph generation with linear delay. Theoretical Computer Science, 713:1–10, 2018. 39

    2018

  130. [138]

    K. F. Jones. Independence in graphs with maximum degree four.Journal of Combinatorial Theory, Series B, 37(3):254–269, 1984

    1984

  131. [139]

    Junttila and P

    T. Junttila and P. Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 135–149. SIAM, 2007

    2007

  132. [140]

    Junttila and P

    T. Junttila and P. Kaski. Conflict propagation and component recursion for canonical labeling. InInternational Conference on Theory and Practice of Algorithms in (Computer) Systems, pages 151–162. Springer, 2011

    2011

  133. [141]

    F. Kardoš. A Computer-Assisted Proof of the Barnette–Goodey Conjecture: Not Only Fullerene Graphs Are Hamiltonian.SIAM Journal on Discrete Mathematics, 34(1):62–100, 2020

    2020

  134. [142]

    Karmarkar

    N. Karmarkar. A new polynomial-time algorithm for linear programming. InProceedings of the sixteenth annual ACM Symposium on Theory of Computing, pages 302–311, 1984

    1984

  135. [143]

    R. M. Karp.Reducibility among combinatorial problems, pages 85–103. New York: Plenum, 1972

    1972

  136. [144]

    Katebi, K

    H. Katebi, K. A. Sakallah, and I. L. Markov. Symmetry and satisfiability: An update. In International Conference on Theory and Applications of Satisfiability Testing, pages 113–127. Springer, 2010

    2010

  137. [145]

    O.-H. Keller. Über die lückenlose Erfüllung des Raumes mit Würfeln.Journal für die reine und angewandte Mathematik, 163:231–248, 1930

    1930

  138. [146]

    L. G. Khachiyan. Polynomial algorithms in linear programming.USSR Computational Mathematics and Mathematical Physics, 20(1):53–72, 1980

    1980

  139. [147]

    Kirchweger and S

    M. Kirchweger and S. Szeider. SAT Modulo Symmetries for Graph Generation and Enumeration. ACM Transactions on Computational Logic, 25(3):1–30, 2024

    2024

  140. [148]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt Jr, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671–680, 1983

    1983

  141. [149]

    D. E. Knuth.The Art of Computer Programming, volume 3. Pearson Education, 1997

    1997

  142. [150]

    Kobler, U

    J. Kobler, U. Schöning, and J. Torán.The graph isomorphism problem: its structural complexity. Springer Science & Business Media, 2012

    2012

  143. [151]

    D. L. Kreher and D. R. Stinson. Combinatorial algorithms: generation, enumeration, and search. ACM SIGACT News, 30(1):33–35, 1999

    1999

  144. [152]

    H. W. Kroto, J. R. Heath, S. C. O’Brien, R. F. Curl, and R. E. Smalley.C60: Buckmin- sterfullerene. Nature, 318(6042):162–163, 1985

    1985

  145. [153]

    Kullmann

    O. Kullmann. On a generalization of extended resolution.Discrete Applied Mathematics, 96:149–176, 1999. 40

    1999

  146. [154]

    C. W. H. Lam, L. Thiel, and S. Swiercz. The non-existence of finite projective planes of order 10. Canadian Journal of Mathematics, 41(6):1117–1123, 1989

    1989

  147. [155]

    M. Lapan. Deep Reinforcement Learning Hands-On: Apply modern RL methods to practical problems of chatbots, robotics, discrete optimization, web automation, and more. Packt Publishing Ltd, 2020

    2020

  148. [156]

    Lidický and F

    B. Lidický and F. Pfender. Pentagons in triangle-free graphs. European Journal of Combinatorics, 74:85–89, 2018

    2018

  149. [157]

    Lidický and F

    B. Lidický and F. Pfender. Semidefinite programming and Ramsey numbers.SIAM Journal on Discrete Mathematics, 35(4):2328–2344, 2021

    2021

  150. [158]

    J. L. López-Presa, L. N. Chiroque, and A. Fernández Anta. Novel techniques for auto- morphism group computation. InInternational Symposium on Experimental Algorithms, pages 296–307. Springer, 2013

    2013

  151. [159]

    J. L. López-Presa and A. Fernández Anta. Fast algorithm for graph isomorphism testing. In International Symposium on Experimental Algorithms, pages 221–232. Springer, 2009

    2009

  152. [160]

    Lougee-Heimer

    R. Lougee-Heimer. The Common Optimization INterface for Operations Research: Pro- moting open-source software in the operations research community.IBM Journal of Research and Development, 47(1):57–66, 2003

    2003

  153. [161]

    L. Lovász. A characterization of perfect graphs.Journal of Combinatorial Theory, Series B, 13(2):95–98, 1972

    1972

  154. [162]

    Loz and J

    E. Loz and J. Širáň. New record graphs in the degree-diameter problem.Australasian Journal of Combinatorics, 41:63, 2008

    2008

  155. [163]

    E. M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, 25(1):42–65, 1982

    1982

  156. [164]

    Máčajová and G

    E. Máčajová and G. Mazzuoccolo. Reduction of the Berge-Fulkerson conjecture to cyclically 5-edge-connected snarks.Proceedings of the American Mathematical Society, 148(11):4643–4652, 2020

    2020

  157. [165]

    J. Mackey. A cube tiling of dimension eight with no facesharing.Discrete & Computational Geometry, 28(2):275–279, 2002

    2002

  158. [166]

    Maplesoft, a division of Waterloo Maple Inc. Maple. Waterloo, Ontario

  159. [167]

    L. R. Matheson and R. E. Tarjan. Dominating sets in planar graphs.European Journal of Combinatorics, 17(6):565–568, 1996

    1996

  160. [168]

    R. Mathon. A note on the graph isomorphism counting problem.Information Processing Letters, 8(3):131–136, 1979

    1979

  161. [169]

    Mayhew and G

    D. Mayhew and G. F. Royle. Matroids with nine elements.Journal of Combinatorial Theory, Series B, 98(2):415–431, 2008. 41

    2008

  162. [170]

    B. D. McKay. Combinatorial data. URL:https://users.cecs.anu.edu.au/~bdm/data/ (accessed 2025-08-08)

    2025

  163. [171]

    B. D. McKay. Practical graph isomorphism.Congressus Numerantium, 30:45–87, 1981

    1981

  164. [172]

    B. D. McKay. Isomorph-free exhaustive generation.Journal of Algorithms, 26(2):306–324, 1998

    1998

  165. [173]

    B. D. McKay, A. Meynert, and W. Myrvold. Small Latin squares, quasigroups, and loops. Journal of Combinatorial Designs, 15(2):98–119, 2007

    2007

  166. [174]

    B. D. McKay, W. Myrvold, and J. Nadon. Fast backtracking principles applied to find new cages. InSymposium on Discrete Algorithms (SODA), pages 188–191, 1998

    1998

  167. [175]

    B. D. McKay and A. Piperno.nauty user guide. URL: https://users.cecs.anu.edu. au/~bdm/nauty/ (accessed 2025-08-08)

    2025

  168. [176]

    B. D. McKay and A. Piperno. Practical graph isomorphism, II.Journal of Symbolic Computation, 60:94–112, 2014

    2014

  169. [177]

    B. D. McKay and E. Spence. Classification of regular two-graphs on 36 and 38 vertices. Australasian Journal of Combinatorics, 24:293–300, 2001

    2001

  170. [178]

    B. D. McKay and I. M. Wanless. On the number of Latin squares.Annals of Combinatorics, 9(3):335–344, 2005

    2005

  171. [179]

    B. D. McKay, M. A. Yirik, and C. Steinbeck. Surge: a fast open-source chemical graph generator. Journal of Cheminformatics, 14(1):24, 2022

    2022

  172. [180]

    Meringer

    M. Meringer. Regular graphs page. URL: https://www.mathe2.uni-bayreuth.de/ markus/reggraphs.html (accessed 2025-08-08)

    2025

  173. [181]

    Meringer

    M. Meringer. Fast generation of regular graphs and construction of cages.Journal of Graph Theory, 30(2):137–146, 1999

    1999

  174. [182]

    R. Merris. Split graphs.European Journal of Combinatorics, 24(4):413–430, 2003

    2003

  175. [183]

    G. Miller. Isomorphism testing for graphs of bounded genus. InProceedings of the twelfth annual ACM Symposium on Theory of Computing, pages 225–235, 1980

    1980

  176. [184]

    Miller and J

    M. Miller and J. Širáň. Moore graphs and beyond: A survey of the degree/diameter problem. Electronic Journal of Combinatorics, DS14–May, 2012

    2012

  177. [185]

    Minchenko and I

    M. Minchenko and I. M. Wanless. Quartic integral Cayley graphs.Ars Mathematica Contemporanea, 8(2), 2015

    2015

  178. [186]

    Mladenović and P

    N. Mladenović and P. Hansen. Variable neighborhood search.Computers & Operations Research, 24:1097–1100, 1997

    1997

  179. [187]

    The MOSEK optimization toolbox for Python manual

    MOSEK ApS. The MOSEK optimization toolbox for Python manual. Version 10.0, 2022. https://docs.mosek.com/. 42

    2022

  180. [188]

    Muzychuk

    M. Muzychuk. A solution of the isomorphism problem for circulant graphs.Proceedings of the London Mathematical Society, 88(1):1–41, 2004

    2004

  181. [189]

    Myrvold and J

    W. Myrvold and J. Woodcock. A large set of torus obstructions and how they were discovered. Electronic Journal of Combinatorics, 25:P1.16, 2018

    2018

  182. [190]

    Nešetřil and P

    J. Nešetřil and P. O. De Mendez. Structural properties of sparse graphs. InBuilding Bridges: Between Mathematics and Computer Science, pages 369–426. Springer, 2008

    2008

  183. [191]

    Nethercote and J

    N. Nethercote and J. Seward. Valgrind: a framework for heavyweight dynamic binary instrumentation. ACM SIGPLAN Notices, 42(6):89–100, 2007

    2007

  184. [192]

    Nishizeki and N

    T. Nishizeki and N. Chiba.Planar graphs: Theory and Algorithms, volume 32. Elsevier, 1988

    1988

  185. [193]

    Novikov, N

    A. Novikov, N. V˜ u, M. Eisenberger, E. Dupont, P.-S. Huang, A. Z. Wagner, S. Shirobokov, B. Kozlovskii, F. J. Ruiz, A. Mehrabian, M. P. Kumar, A. See, S. Chaudhuri, G. Holland, A. Davies, S. Nowozin, P. Kohli, and M. Balog. AlphaEvolve: A coding agent for scientific and algor...

    2025 arXiv

  186. [194]

    Entry A000088 in The On-Line Encyclopedia of Integer Sequences

    OEIS Foundation Inc. Entry A000088 in The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A000088, 2025. Published electronically

    2025

  187. [195]

    Entry A000109 in The On-Line Encyclopedia of Integer Sequences

    OEIS Foundation Inc. Entry A000109 in The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A000109, 2025. Published electronically

    2025

  188. [196]

    Entry A000944 in The On-Line Encyclopedia of Integer Sequences

    OEIS Foundation Inc. Entry A000944 in The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A000944, 2025. Published electronically

    2025

  189. [197]

    Entry A007022 in The On-Line Encyclopedia of Integer Sequences

    OEIS Foundation Inc. Entry A007022 in The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A007022, 2025. Published electronically

    2025

  190. [198]

    Penttila, G

    T. Penttila, G. F. Royle, and M. K. Simpson. Hyperovals in the known projective planes of order 16.Journal of Combinatorial Designs, 4(1):59–65, 1996

    1996

  191. [199]

    O. Perron. Über lückenlose Ausfüllung desn-dimensionalen Raumes durch kongruente Würfel. Mathematische Zeitschrift, 46(1):1–26, 1940

    1940

  192. [200]

    O. Perron. Über lückenlose Ausfüllung desn-dimensionalen Raumes durch kongruente Würfel. II. Mathematische Zeitschrift, 46(1):161–180, 1940

    1940

  193. [201]

    A. Piperno. Search space contraction in canonical labeling of graphs.arXiv preprint arXiv:0804.4881, 2008

    2008 arXiv

  194. [202]

    Pirot and J.-S

    F. Pirot and J.-S. Sereni. Fractional chromatic number, maximum degree, and girth. SIAM Journal on Discrete Mathematics, 35(4):2815–2843, 2021

    2021

  195. [203]

    Pisanski, D

    T. Pisanski, D. Marušič, P. Potočnik, A. Orbanić, B. Horvat, and P. Lukšič. The Encyclopedia of Graphs. URL:http://atlas.gregas.eu (accessed 2025-08-08)

    2025

  196. [204]

    Potočnik

    P. Potočnik. Dataset of highly symmetric objects. URL:http://graphsym.net (accessed 2025-08-08). 43

    2025

  197. [205]

    Potočnik

    P. Potočnik. A list of 4-valent 2-arc-transitive graphs and finite faithful amalgams of index (4, 2). European Journal of Combinatorics, 30(5):1323–1336, 2009

    2009

  198. [206]

    Potočnik, P

    P. Potočnik, P. Spiga, and G. Verret. Cubic vertex-transitive graphs on up to 1280 vertices. Journal of Symbolic Computation, 50:465–477, 2013

    2013

  199. [207]

    Potočnik, P

    P. Potočnik, P. Spiga, and G. Verret. Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs.Journal of Combinatorial Theory, Series B, 111:148–180, 2015

    2015

  200. [208]

    Potočnik and S

    P. Potočnik and S. E. Wilson. Recipes for edge-transitive tetravalent graphs.The Art of Discrete and Applied Mathematics, 3(1):#P1.08, 2020

    2020

  201. [209]

    Radziszowski

    S. Radziszowski. Small Ramsey numbers.Electronic Journal of Combinatorics, DS1–Jan, 2012

    2012

  202. [210]

    F. P. Ramsey. On a Problem of Formal Logic.Proceedings of the London Mathematical Society, S2-30(1):264, 1930

    1930

  203. [211]

    M. Randić. Characterization of molecular branching.Journal of the American Chemical Society, 97(23):6609–6615, 1975

    1975

  204. [212]

    A. A. Razborov. Flag algebras.The Journal of Symbolic Logic, 72(4):1239–1282, 2007

    2007

  205. [213]

    R. C. Read. Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations. InAnnals of Discrete Mathematics, volume 2, pages 107–120. Elsevier, 1978

    1978

  206. [214]

    C. Reiher. The clique density theorem.Annals of Mathematics, pages 683–707, 2016

    2016

  207. [215]

    Robertson, D

    N. Robertson, D. Sanders, P. Seymour, and R. Thomas. The Four-Colour Theorem. Journal of Combinatorial Theory, Series B, 70(1):2–44, 1997

    1997

  208. [216]

    Romera-Paredes, M

    B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. P. Kumar, E. Dupont, F. J. R. Ruiz, J. S. Ellenberg, P. Wang, O. Fawzi, P. Kohli, and A. Fawzi. Mathematical discoveries from program search with large language models.Nature, 625(7995):468–475, 2024

    2024

  209. [217]

    R. A. Rossi and N. K. Ahmed. The network data repository with interactive graph analytics and visualization. InTwenty-Ninth Conference on Artificial Intelligence (AAAI-15), 2015

    2015

  210. [218]

    E. F. Schmeichel and S. L. Hakimi. On planar graphical degree sequences.SIAM Journal on Applied Mathematics, 32(3):598–609, 1977

    1977

  211. [219]

    P. D. Seymour. Sums of circuits. InGraph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977), pages 341–355. Academic Press, New York-London, 1979

    1977

  212. [220]

    J. B. Shearer. A note on the independence number of triangle-free graphs, II.Journal of Combinatorial Theory, Series B, 53(2):300–307, 1991. 44

    1991

  213. [221]

    J. Sheehan. The multiplicity of hamiltonian circuits in a graph.Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), Academia, Prague, pages 477–480, 1975

    1974

  214. [222]

    E. Spence. Combinatorial data. URL:https://www.maths.gla.ac.uk/~es/ (accessed 2025-08-08)

    2025

  215. [223]

    E. Spence. The strongly regularp40, 12, 2, 4q graphs. Electronic Journal of Combinatorics, 7:R22, 2000

    2000

  216. [224]

    W. Staton. Some Ramsey-type numbers and the independence ratio.Transactions of the American Mathematical Society, 256:353–370, 1979

    1979

  217. [225]

    T. Sulanke. Generating maps on surfaces.Discrete & Computational Geometry, 57(2):335– 356, 2017

    2017

  218. [226]

    R. S. Sutton and A. G. Barto.Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998

    1998

  219. [227]

    Szekeres

    G. Szekeres. Polyhedral decompositions of cubic graphs. Bulletin of the Australian Mathematical Society, 8:367–387, 1973

    1973

  220. [228]

    P. Taylor. Halin graphs. URL:https://cheddarmonk.org/maths/halin_graphs/ (ac- cessed 2025-08-08)

    2025

  221. [229]

    Tener and N

    G. Tener and N. Deo. Efficient isomorphism of Miyazaki graphs. In39th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, 2008

    2008

  222. [230]

    Groups, Algorithms, and Programming

    The GAP Group. Groups, Algorithms, and Programming. URL:http://www.gap-system. org (accessed 2025-08-08)

    2025

  223. [231]

    An index of mathematical databases

    The MathBases Developers. An index of mathematical databases. URL: https:// mathbases.org/ (accessed 2025-08-08)

    2025

  224. [232]

    Sagemath, the Sage Mathematics Software System (version 9.5)

    The Sage Developers. Sagemath, the Sage Mathematics Software System (version 9.5). URL: https://www.sagemath.org (accessed 2025-08-08)

    2025

  225. [233]

    W. T. Tutte. A contribution to the theory of chromatic polynomials.Canadian Journal of Mathematics, 6:80–91, 1954

    1954

  226. [234]

    Van den Camp and B

    H. Van den Camp and B. D. McKay. Generating plane quadrangulations and symmetry- preserving operations on maps.Discrete Mathematics & Theoretical Computer Science, 26(Discrete Algorithms), 2024

    2024

  227. [235]

    Vandenberghe and S

    L. Vandenberghe and S. Boyd. Semidefinite programming.SIAM Review, 38(1):49–95, 1996

    1996

  228. [236]

    Vaughan.Flagmatic 2.0, 2012

    E. Vaughan.Flagmatic 2.0, 2012. https://github.com/emil79/flagmatic

    2012

  229. [237]

    A. Z. Wagner. Refuting conjectures in extremal combinatorics via linear programming. Journal of Combinatorial Theory, Series A, 169:105130, 2020. 45

    2020

  230. [238]

    A. Z. Wagner. Constructions in combinatorics via neural networks. arXiv preprint arXiv:2104.14516, 2021

    2021 arXiv

  231. [239]

    I. M. Wanless. Combinatorial data. URL:https://users.monash.edu.au/~iwanless/ data/ (accessed 2025-08-08)

    2025

  232. [240]

    G. Wegner. Graphs with given diameter and a coloring problem.Technical report, 1977

    1977

  233. [241]

    Weisfeiler and A

    B. Weisfeiler and A. A. Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction.Nauchno-Technicheskaya Informatsiya, 2(9):12–16, 1968

    1968

  234. [242]

    Wetzler, M

    N. Wetzler, M. J. H. Heule, and W. A. Hunt Jr. DRAT-trim: Efficient checking and trimming using expressive clausal proofs. InInternational Conference on Theory and Applications of Satisfiability Testing, pages 422–429. Springer, 2014

    2014

  235. [243]

    H. Wiener. Structural Determination of Paraffin Boiling Points.Journal of the American Chemical Society, 69(1):17–20, 1947

    1947

  236. [244]

    Mathematica, Version 14.2

    Wolfram Research, Inc. Mathematica, Version 14.2. URL:https://www.wolfram.com/ mathematica (accessed 2025-08-08). Champaign, IL, 2024

    2025

  237. [245]

    L. A. Wolsey.Integer programming. John Wiley & Sons, 2020

    2020

  238. [246]

    W. Xia, J. Jooken, J. Goedgebeur, and S. Huang. Critical (P5, dart)-free graphs.Discrete Applied Mathematics, 366:44–52, 2025

    2025

  239. [247]

    W. Xia, J. Jooken, J. Goedgebeur, and S. Huang. Some results on critical (P5, H)-free graphs. Theoretical Computer Science, 1051:115411, 2025

    2025

  240. [248]

    Yamashita, K

    M. Yamashita, K. Fujisawa, K. Nakata, M. Nakata, M. Fukuda, K. Kobayashi, and K. Goto. A high-performance software package for semidefinite programs: SDPA 7, 2010

    2010

  241. [249]

    Yamazaki, M

    K. Yamazaki, M. Qian, and R. Uehara. Efficient enumeration of non-isomorphic distance- hereditary graphs and Ptolemaic graphs. InWALCOM: Algorithms and Computation: 15th International Conference and Workshops, WALCOM 2021, Yangon, Myanmar, February 28–March 2, 2021, Proceeding...

    2021

  242. [250]

    Yamazaki, T

    K. Yamazaki, T. Saitoh, M. Kiyomi, and R. Uehara. Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs.Theoretical Computer Science, 806:310–322, 2020. 46

    2020

Pith tools

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