TOPICS
Search

Schurian Graph


A Schurian graph is a finite graph X for which the coherent configuration determined by the stable coloring produced by the two-dimensional Weisfeiler-Leman algorithm is Schurian. Equivalently, a finite graph is Schurian when these color classes are exactly the orbitals of the componentwise group action of the automorphism group Aut(X) on ordered pairs of vertices (Li et al. 2026).

A stable coloring is one that color refinement does not split further. When the associated coherent configuration is a homogeneous coherent configuration, it is a Schurian scheme. Li et al. (2026) proved that every Schurian polyhedral graph has Weisfeiler-Leman dimension at most 2 and conjectured that every polyhedral graph is Schurian.

Reh (2026) reported an exhaustive computer verification that all 413024847068 polyhedral graphs with at most 16 vertices are Schurian. This verifies a finite range of the conjecture, not the unrestricted assertion. Reh (2026) states that Claude assisted with implementation, verification design, and drafting.


See also

Coherent Configuration, Graph Automorphism, Homogeneous Coherent Configuration, Orbital, Polyhedral Graph, Schurian Coherent Configuration, Schurian Scheme, Stable Coloring, Weisfeiler-Leman Algorithm, Weisfeiler-Leman Dimension

Explore with Wolfram|Alpha

References

Li, H.; Ponomarenko, I.; and Zeman, P. "On the Weisfeiler-Leman Dimension of Some Polyhedral Graphs." Elec. J. Combin. 33, P3.25, 2026. https://doi.org/10.37236/13936.Reh, D. "All Polyhedral Graphs with at Most 16 Vertices Are Schurian: A Computational Verification." 4 Sep 2026. https://arxiv.org/abs/2610.03729.

Cite this as:

Weisstein, Eric W. "Schurian Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SchurianGraph.html

Subject classifications