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, the color classes are exactly the orbits of the componentwise action of the automorphism group Aut(X) on ordered pairs of vertices (Li et al. 2026).

When the associated coherent configuration is homogeneous, 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, Polyhedral Graph, Schurian Coherent Configuration, Schurian Scheme, 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