Pith. sign in

REVIEW 2 major objections 4 minor 36 references

The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs

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

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

Pith's one-line read The two-dimensional Weisfeiler-Leman algorithm implicitly computes the decomposition of a graph into its 3-connected components.

desk verdict A genuinely strong paper with a real gap: the separator detection and treewidth bounds are solid, but the headline decomposition theorem is only sketched and rests on unstated strengthened lemmas. read the letter →

arxiv 1908.05268 v2 pith:5V7YLIVJ submitted 2019-08-14 cs.DM cs.LOmath.CO

Sandra Kiefer , Daniel Neuen This is my paper · ORCID
classification cs.DMcs.LOmath.CO MSC 05C6005C4005C75
keywords Weisfeiler-LemanalgorithmgraphisomorphismtriconnecteddecompositionseparatordetectiontreewidthassociationschemescountinglogicC3WLdimension
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 paper establishes that the Weisfeiler-Leman (WL) algorithm detects connectivity structure from dimension 2 upward: if a k-tuple of vertices separates a graph, no graph can give that k-tuple the same WL-k color unless the corresponding tuple separates it too. The authors use this to prove that the 2-dimensional WL algorithm implicitly computes the classical decomposition of a graph into its 3-connected components, so the dimension needed to distinguish two graphs is at most the dimension needed to distinguish their pieces. They then apply the decomposition to graphs of treewidth at most k, proving the k-dimensional WL algorithm identifies every such graph, and they show via a standard lower-bound construction that the WL dimension of treewidth-k graphs lies between $\lceil k/2\rceil - 3$ and $k$. As a byproduct, every connected constituent graph of an association scheme is either a cycle or 3-connected, a fact previously known only for the more restricted symmetric case.

What carries the argument

The load-bearing object is the stable tuple coloring $\chi_{G,k}$ produced by the k-dimensional WL algorithm, which refines the coloring of vertex tuples by repeatedly counting, for each tuple, the multiset of colors obtained by replacing one coordinate by every vertex. Around that object, the paper's main tool is the auxiliary graph $G[[S]]$: its vertices are the vertices of $G$ whose diagonal color lies in a set $S$, and two such vertices are adjacent when connected by a path in $G$ that avoids $S$. The WL algorithm detects such paths, so $G[[S]]$ inherits stable colors; the proof shows that a 2-separator in $G$ forces $G[[S]]$ to be a cycle in the uniform-color cases, forcing $H[[S]]$ to be a cycle too, which is what transfers the separator property from $G$ to $H$. The edge-maximality argument used throughout the structural lemmas is the mechanism that rules out all non-cycle configurations.

What would settle it

Find two 2-connected graphs $G$ and $H$ such that the stable 2-dimensional WL color of a separating pair in $G$ equals the color of a non-separating pair in $H$; such a pair would refute Theorem 5.2, the technical heart of the paper, because the entire decomposition program reduces to that statement.

Watch

Extended reading notes

Core claim

The central claim appears in Corollary 5.3: for all $k \ge 2$, the k-dimensional WL algorithm distinguishes k-separators from other k-tuples of vertices. The proof for $k = 2$ first shows that any graph whose stable WL coloring gives one color to all vertices and that contains a 2-separator must be a cycle (Theorem 3.9), then extends the same conclusion to graphs with two vertex colors (Theorem 4.5). These uniform-color cases are lifted to arbitrary graphs through the graph $G[[S]]$, which connects vertices of a chosen color set $S$ by paths that avoid $S$; the 2-dimensional WL algorithm can see these paths, so a 2-separator in $G$ forces the corresponding tuple in any WL-equivalent graph $H$ to separate $H$ as well (Theorem 5.2). The final theorem (Theorem 5.4) states the payoff: in a minor-closed graph class, if the k-dimensional WL algorithm determines orbits on all arc-colored 3-connected graphs in the class, then it distinguishes all non-isomorphic graphs in the class.

Load-bearing premise

The proof of Theorem 5.4 rests on a sketched strengthening of Lemmas 17 and 18 from the earlier planar-graph work, moving from dimension 3 to dimension 2; the paper does not state or prove those strengthened lemmas, and if that step fails, the advertised decomposition theorem would not follow from the arguments given.

Editorial extensions

If this is right

  • For every $k \ge 2$, a k-separator in $G$ can share its WL-k color with a tuple in $H$ only if that tuple is also a k-separator of $H$.
  • For any minor-closed graph class, the WL dimension is bounded by the dimension needed to determine orbits on its arc-colored 3-connected graphs; the decomposition step adds no extra dimension.
  • The WL dimension of graphs of treewidth at most $k$ lies between $\lceil k/2\rceil - 3$ and $k$, improving the previous upper bound of $k+2$ and matching the lower bound up to a factor of 2.
  • Two non-isomorphic graphs can be told apart by the k-dimensional WL algorithm ($k \ge 2$) as soon as their decompositions into 3-connected components are told apart.
  • Connected constituent graphs of association schemes are cycles or 3-connected, and the sizes of the components left by deleting a 2-separator are expressible in the three-variable counting logic $C^3$.

Reading between the lines

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

  • I read the paper's closing conjecture as the natural next test: if the 2-dimensional WL algorithm determines orbits on all 3-connected planar graphs, Theorem 5.4 would imply that it identifies every planar graph, settling the open 2-versus-3 question for planar graphs.
  • A fully formal proof of Theorem 5.4 still requires stating and proving the strengthened versions of Lemmas 17 and 18 from the earlier planar-graph work; the paper marks this as requiring more work and leaves the details out.
  • Because the separator relation is definable in $C^3$, graph representations built on 2-WL colors inherit a decomposition-aware signal; one could test this by comparing 2-WL-based embeddings with explicit 3-connected-component features on graph-separation benchmarks.
  • The subdivided-grid lower-bound pair suggests the true WL dimension of treewidth-$k$ graphs may be closer to $k/2$ than to $k$; computing the exact dimension for small $k$, say $k = 4$ or $5$, would show whether the factor-2 gap is an artifact.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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 paper studies the expressive power of the Weisfeiler-Leman (WL) algorithm. It proves that for k ≥ 2, the k-dimensional WL algorithm distinguishes k-separators from other k-tuples, and specifically that the 2-dimensional algorithm detects 2-separators. Building on this, it claims that the k-dimensional WL algorithm implicitly computes the decomposition of a graph into its 3-connected components, which would imply that distinguishing graphs in a minor-closed class reduces to distinguishing arc-colored 3-connected graphs in that class. The paper further derives that connected constituent graphs of association schemes are either cycles or 3-connected, and it applies the separator results to prove a new upper bound of k on the WL dimension of graphs of treewidth at most k, together with a lower bound that is within a factor of 2 of the upper bound.

Significance. The separator-detection results are solid and valuable: Sections 3 through 5 up to Corollary 5.3 and Theorem 5.5 contain detailed, largely self-contained proofs, and the association-scheme corollary is a genuine new structural insight. If Theorem 5.4 were fully proved, the decomposition theorem would be a significant step toward settling the WL dimension of planar graphs and would unify several dimension bounds. The treewidth upper bound is a clean improvement over the previous k + 2, and the lower bound is asymptotically tight up to a factor of 2, although the color-encoding issue raised below needs clarification.

major comments (2)
  1. [Section 5, Theorem 5.4 (proof sketch)] The paper's central decomposition claim is not established as written. The proof sketch explicitly states that showing the partition induced by χ^k_G on V(G⊥) is finer than λ⊥ "requires some more work, breaking down to strengthening Lemma 18 in [27]", and the only indication is that Corollary 5.3 lets one replace χ^k_G(s1,s2,v) by χ^k_G(s1,v). No strengthened statement of [27, Lemmas 17 and 18] is formulated, and no proof is supplied for the strengthened induction. Since [27] proves these lemmas only for dimension 3, the advertised implication—that orbit-determination on arc-colored 3-connected graphs implies distinguishing all graphs in a minor-closed class—is conditional on deferred technical work. Corollary 5.3, Theorem 5.5, and Theorem 6.3 do not substitute for this step, because they do not address the interaction of multiple separators in the decomposition tree.
  2. [Section 6.2, Theorem 6.8 and Corollary 6.9] The CFI construction yields vertex-colored graphs, while Corollary 6.9 is a statement about the WL dimension of the uncolored class T_k. The paper does not describe how the vertex colors in CFI(G_{n,n}) and CFI_x(G_{n,n}) are removed (for instance, by a standard color-encoding gadget), nor how such a removal affects treewidth. Without this clarification, the lower bound may only apply to colored graphs and would not directly bound dim_WL(T_k).
minor comments (4)
  1. [Section 5, proof of Theorem 5.4] The proof sketch says "suppose the 2-dimensional WL algorithm determines orbits" although the theorem is stated for arbitrary k ≥ 2; this should be "k-dimensional".
  2. [Section 6.3, proof of Theorem 6.3] Some displayed formulas have unbalanced parentheses, for example "G[A_i ∪ ¯a ∪ {v}], ¯a, v)" and "H[B_i ∪ ¯b ∪ {w}], ¯b, w)"; please fix the typesetting.
  3. [Corollary 5.3, last paragraph] The reduction to the 2-dimensional case for k > 2 is stated in a single sentence and deserves a more detailed justification that the first k−2 vertices can be chosen so that the remaining pair is a 2-separator in the reduced graph and that the color equality is preserved under this reduction.
  4. [Section 4, proof of Theorem 4.5] In Claim 1, phrases such as "It is not hard to see" and "by regularity" compress several counting arguments; expanding these steps would improve verifiability.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the paper derives separator detection from new graph-theoretic arguments, and its reliance on prior same-author work is a proof-completeness gap rather than a reduction to the target claim.

full rationale

The central new claim, that for k >= 2 the k-dimensional Weisfeiler-Leman algorithm distinguishes k-separators from other k-tuples, is not obtained by assuming the conclusion. Corollary 5.3 rests on Theorem 5.2, which is proved from the structural characterizations in Sections 3 and 4: under a stable two-vertex-coloring, a connected graph with a 2-separator must be a cycle, and two-colored 2-connected graphs with compatible vertex colors have the same forced structure. These proofs are self-contained and use standard facts about the WL algorithm and pebble games, together with external results such as [27, Theorem 6] and [27, Corollary 7] about cut vertices and 2-connected components. Those cited facts are earlier independent results, not the target theorem, and they are not the mechanism by which the 2-separator detection conclusion is defined into existence. The treewidth upper bound in Theorem 6.3 is proved with a direct pebble-game strategy using the Arnborg-Corneil-Proskurowski characterization [1], and the lower bound uses the CFI construction and Dawar-Richerby [10]; neither involves fitting or renaming. The genuine weakness of the paper is different: the advertised decomposition theorem (Theorem 5.4) is only sketched, and the sketch explicitly delegates the hard part to an unproved strengthening of Lemma 18 in [27], saying only that it 'requires some more work.' This is an internal completeness gap: as written, the theorem is conditional on deferred technical work. But the deferred work is not identical to the theorem's conclusion, and no equation or definition in the paper forces the claimed result to equal its own input. Therefore the paper is not circular; it is incomplete in a specific, repairable place.

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

The paper introduces no free parameters or invented entities. It relies on standard results from the WL/pebble-game literature and on prior structural lemmas from [27], which are cited as established. The main undeclared support is the set of strengthened lemmas from [27] that Theorem 5.4 assumes without full proof.

assumptions (5)
  • standard math Bijective pebble game characterization of WL-equivalence (Theorem 2.1).
    Cites [9] and states the correspondence between WL and pebble games; used throughout the paper to analyze the algorithm.
  • domain assumption The 2-dimensional WL algorithm detects cut vertices and distances (from [27, Corollary 7]).
    Invoked in Lemma 3.3 and other arguments; relies on prior work by the authors of this paper.
  • standard math Tree-decomposition characterization of treewidth (Lemma 6.2 from Arnborg et al. [1]).
    Used in the treewidth upper bound proof in Section 6.1.
  • standard math Dawar-Richerby lower bound theorem for CFI graphs (Theorem 6.5 from [10]).
    Used to obtain the treewidth lower bound in Section 6.2.
  • standard math Cai-Furer-Immerman gadget properties (Lemma 6.4 from [9]).
    Used to construct the lower-bound graphs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs." pith.science (2026). https://pith.science/paper/5V7YLIVJ

@misc{pith2026190805268,
  author       = {Pith},
  title        = {Pith review of: The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5V7YLIVJ}},
  note         = {Machine review of arXiv:1908.05268}
}
read the original abstract

The Weisfeiler-Leman procedure is a widely-used technique for graph isomorphism testing that works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Meanwhile, a fundamental tool in structural graph theory, which is often exploited in approaches to tackle the graph isomorphism problem, is the decomposition into 2- and 3-connected components. We prove that the 2-dimensional Weisfeiler-Leman algorithm implicitly computes the decomposition of a graph into its 3-connected components. This implies that the dimension of the algorithm needed to distinguish two given non-isomorphic graphs is at most the dimension required to distinguish non-isomorphic 3-connected components of the graphs (assuming dimension at least 2). To obtain our decomposition result, we show that, for k >= 2, the k-dimensional algorithm distinguishes k-separators, i.e., k-tuples of vertices that separate the graph, from other vertex k-tuples. As a byproduct, we also obtain insights about the connectivity of constituent graphs of association schemes. In an application of the results, we show the new upper bound of k on the Weisfeiler-Leman dimension of the class of graphs of treewidth at most k. Using a construction by Cai, F\"urer, and Immerman, we also provide a new lower bound that is asymptotically tight up to a factor of 2.

Figures

Figures reproduced from arXiv: 1908.05268 by the authors.

Figure 1
Figure 1. Visualization of the sets Ci,j for d = 4 in the proof of Lemma 3.8. Each arc between two sets indicates that there may be edges connecting vertices from the two sets. Overall, this means that, on the one hand, dist(w1, u) ≤ d for all u ∈ V (G). On the other hand, there is a u ∈ C ′ such that dist(w1, u) ≥ 2 because d ≥ 3. But then dist(v, u) ≥ d + 1 for v ∈ Cd,d ∪ Cd−1,d. So D(w1) 6= D(v), which is a contradiction. … view at source ↗
Figure 2
Figure 2. Visualization of the set Ci,j for d = 5 in the proof of Theorem 4.5. Each edge between two sets indicates that there may be edges connecting vertices from the two sets. be two shortest paths from u to w1 or two shortest paths from u to w2, contradicting Claim 2. Now suppose towards a contradiction that deg(u) > 2. Then there is a v ∈ N(u) ∩ C5,d−3. We have that N(v) ⊆ C4,d−4 ∪ C4,d−2 ∪ C6,d−4 ∪ C6,d−2. Using Claim 2… view at source ↗
Figure 3
Figure 3. Visualization of the set Ci,j for d = 3 in the proof of Theorem 4.5. Each edge between two sets indicates that there may be edges connecting vertices from the two sets. Therefore, analogously as in the proof of Claim 2, using the edge maximality of G, we can show that there cannot be cycles of length at most 10 in G and that thus, there must be a unique shortest path from v to w1. In particular, this implies that |N… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The Cai-Fürer-Immerman gadget X3. for all w ∈ A and {b(w), mA} ∈ E(XS) for all w ∈ S \ A. As an example, the graph X3 := X[3] is depicted in [PITH_FULL_IMAGE:figures/full_fig_p025_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 34 canonical work pages

  1. [27]

    The Weisfeiler-Leman dimension of planar graphs is at most 3

    Sandra Kiefer, Ilia Ponomarenko, and Pascal Schweitze r. The Weisfeiler-Leman dimension of planar graphs is at most 3. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017 , pages 1–12. IEEE Computer Society, 2017

    work page 2017

  2. [1]

    Corneil, and Andrzej Proskurow ski

    Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurow ski. Complexity of finding em- beddings in a k-tree. SIAM J. Algebraic Discrete Methods , 8(2):277–284, April 1987

    work page 1987

  3. [2]

    On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties

    Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On weisfeiler- leman invariance: Subgraph counts and related graph proper ties. CoRR, abs/1811.04801, 2018

    work page Pith review arXiv 2018

  4. [3]

    Albert Atserias and Elitza N. Maneva. Sherali-Adams rel axations and indistinguishability in counting logics. SIAM J. Comput. , 42(1):112–137, 2013. 27

    work page 2013

  5. [4]

    Graph isomorphism in quasipolynomial tim e [extended abstract]

    László Babai. Graph isomorphism in quasipolynomial tim e [extended abstract]. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Sym- posium on Theory of Computing, STOC 2016, Cambridge, MA, USA, J une 18-21, 2016 , pages 684–697. ACM, 2016

    work page 2016

  6. [5]

    Faster canonical forms for strongly regular graphs

    László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, and J ohn Wilmes. Faster canonical forms for strongly regular graphs. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, C A, USA , pages 157–166. IEEE Computer Society, 2013

    work page 2013

  7. [6]

    Andries E. Brouwer. Spectrum and connectivity of graphs . CWI Quarterly , 9(1-2):37–40, 1996

    work page 1996

  8. [7]

    Brouwer and Jack H

    Andries E. Brouwer and Jack H. Koolen. The vertex-connec tivity of a distance-regular graph. Eur. J. Comb. , 30(3):668–673, 2009

    work page 2009

Show all 36 references
  1. [8]

    Brouwer and Dale M

    Andries E. Brouwer and Dale M. Mesner. The connectivity o f strongly regular graphs. Eur. J. Comb. , 6(3):215–216, 1985

    1985

  2. [9]

    An optimal l ower bound on the number of variables for graph identifications

    Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal l ower bound on the number of variables for graph identifications. Combinatorica, 12(4):389–410, 1992

    1992

  3. [10]

    The power of counting log ics on restricted classes of finite structures

    Anuj Dawar and David Richerby. The power of counting log ics on restricted classes of finite structures. In Jacques Duparc and Thomas A. Henzinger, edit ors, Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerlan...

    2007

  4. [11]

    Lovász me ets Weisfeiler and Leman

    Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász me ets Weisfeiler and Leman. In 45th International Colloquium on Automata, Languages, and Pr ogramming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic , pages 40:1–40:14, 2018

    2018

  5. [12]

    On the vertex co nnectivity of a relation in an association scheme

    Sergei Evdokimov and Ilia Ponomarenko. On the vertex co nnectivity of a relation in an association scheme. Journal of Mathematical Sciences , 134(5):2354–2357, May 2006

    2006

  6. [13]

    On the combinatorial power of the weisfei ler-lehman algorithm

    Martin Fürer. On the combinatorial power of the weisfei ler-lehman algorithm. In Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, editor s, Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings, volume 10...

    2017

  7. [14]

    Fixed-point definability and polynomial time on graphs with excluded minors

    Martin Grohe. Fixed-point definability and polynomial time on graphs with excluded minors. J. ACM , 59(5):27:1–27:64, 2012

    2012

  8. [15]

    Descriptive Complexity, Canonisation, and Definable Graph S tructure The- ory

    Martin Grohe. Descriptive Complexity, Canonisation, and Definable Graph S tructure The- ory. Lecture Notes in Logic. Cambridge University Press, 2017

    2017

  9. [16]

    A linear upper bound on t he weisfeiler-leman dimension of graphs of bounded genus

    Martin Grohe and Sandra Kiefer. A linear upper bound on t he weisfeiler-leman dimension of graphs of bounded genus. In Christel Baier, Ioannis Chatz igiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programmin...

    2019

  10. [17]

    Definability and descri ptive complexity on databases of bounded tree-width

    Martin Grohe and Julian Mariño. Definability and descri ptive complexity on databases of bounded tree-width. In Catriel Beeri and Peter Buneman, edi tors, Database Theory - ICDT ’99, 7th International Conference, Jerusalem, Israel, January 1 0-12, 1999, Proceedings. , volume 15...

    1999

  11. [18]

    Canonisation and definab ility for graphs of bounded rank width

    Martin Grohe and Daniel Neuen. Canonisation and definab ility for graphs of bounded rank width. In 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019 , pages 1–13. IEEE, 2019

    2019

  12. [19]

    Pebble games and linear eq uations

    Martin Grohe and Martin Otto. Pebble games and linear eq uations. J. Symb. Log. , 80(3):797–844, 2015

    2015

  13. [20]

    Logical hierarchies in PTIME

    Lauri Hella. Logical hierarchies in PTIME. Inf. Comput. , 129(1):1–19, 1996

    1996

  14. [21]

    Hopcroft and Robert Endre Tarjan

    John E. Hopcroft and Robert Endre Tarjan. A v 2 algorithm for determining isomorphism of planar graphs. Inf. Process. Lett. , 1(1):32–34, 1971

    1971

  15. [22]

    Hopcroft and Robert Endre Tarjan

    John E. Hopcroft and Robert Endre Tarjan. Isomorphism o f planar graphs. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Tho mas J. Watson Research Center, Yorktown H...

    1972

  16. [23]

    Hopcroft and Robert Endre Tarjan

    John E. Hopcroft and Robert Endre Tarjan. Dividing a gra ph into triconnected components. SIAM J. Comput. , 2(3):135–158, 1973

    1973

  17. [24]

    Hopcroft and Robert Endre Tarjan

    John E. Hopcroft and Robert Endre Tarjan. A V log V algori thm for isomorphism of triconnected planar graphs. J. Comput. Syst. Sci. , 7(3):323–331, 1973

    1973

  18. [25]

    Hopcroft and J

    John E. Hopcroft and J. K. Wong. Linear time algorithm fo r isomorphism of planar graphs (preliminary report). In Robert L. Constable, Robert W. Rit chie, Jack W. Carlyle, and Michael A. Harrison, editors, Proceedings of the 6th Annual ACM Symposium on Theory of Computing, Apr...

    1974

  19. [26]

    Describing Graphs: A First-Order Approach to Graph Canonization, pages 59–81

    Neil Immerman and Eric Lander. Describing Graphs: A First-Order Approach to Graph Canonization, pages 59–81. Springer New York, New York, NY, 1990

    1990

  20. [28]

    Treewidth, Computations and Approximations , volume 842 of Lecture Notes in Computer Science

    Ton Kloks. Treewidth, Computations and Approximations , volume 842 of Lecture Notes in Computer Science . Springer, 1994

    1994

  21. [29]

    Kodalen and William J

    Brian G. Kodalen and William J. Martin. On the connectiv ity of graphs in association schemes. Electr. J. Comb. , 24(4):P4.39, 2017

    2017

  22. [30]

    Brendan D. McKay. Practical graph isomorphism. Congr. Numer. , 30:45–87, 1981

    1981

  23. [31]

    McKay and Adolfo Piperno

    Brendan D. McKay and Adolfo Piperno. Practical graph is omorphism, II. J. Symb. Comput. , 60:94–112, 2014

    2014

  24. [32]

    Towards a practic al k-dimensional weisfeiler-leman algorithm

    Christopher Morris and Petra Mutzel. Towards a practic al k-dimensional weisfeiler-leman algorithm. CoRR, abs/1904.01543, 2019. 29

    1904 arXiv

  25. [33]

    Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe

    Christopher Morris, Martin Ritzert, Matthias Fey, Wil liam L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neu ral: Higher-order graph neural networks. CoRR, abs/1810.02244, 2018

    2018 arXiv

  26. [34]

    Graph isomorphism for unit square graphs

    Daniel Neuen. Graph isomorphism for unit square graphs . In Piotr Sankowski and Chris- tos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, Au- gust 22-24, 2016, Aarhus, Denmark , volume 57 of LIPIcs, pages 70:1–70:17. Schloss Dagstuhl - Leibniz-...

    2016

  27. [35]

    William T. Tutte. Graph theory. Encyclopedia of mathematics and its applications. Addiso n- Wesley Pub. Co., Advanced Book Program, 1984

    1984

  28. [36]

    The reduction of a gr aph to canonical form and the algebra which appears therein

    Boris Weisfeiler and Andrei Leman. The reduction of a gr aph to canonical form and the algebra which appears therein. NTI, Series 2 , 1968. English translation by G. Ryabov available at https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf. 30

    1968

Pith tools

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