Graph Isomorphism problem, Weisfeiler-Leman algorithm and coherent configurations (Part II)

The graph isomorphism problem is a computational problem of deciding whether two given graphs are isomorphic. It’s not known whether the problem can be solved in a polynomial time or it’s an NP- complete. In our lecture we present a well-known Weisfeiller-Leman (WL) algorithm which solves some particular cases of the problem. It will be shown how WL-algorithm yields a special class of colored graphs known as coherent configurations. We’ll show the basic properties of those objects and focus on a special class of them known as association schemes. Association schemes play an important role in algebraic graph theory.