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.


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, No. 3, P3.25, 2026. https://doi.org/10.37236/13936.

Cite this as:

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

Subject classifications