The Weisfeiler-Leman dimension of distance-hereditary graphs (Q6166669)

A graph \(X\) is distance-hereditary if the distance between any two vertices in any connected induced subgraph of \(X\) is the same as in \(X\). The Weisfeiler-Leman algorithm (WL) is a tool for testing isomorphisms of finite graphs. The \(d\)-dimensional Weisfeiler-Leman algorithm (\(d\)-dim WL) is one possible generalization of WL, where the algorithm colors \(d\)-tuples of vertices and then compares numerical invariants of the obtained colorings. The smallest integer \(d_X\), such that for any \(d \geq d_x\) \(d\)-dim WL test isomorphisms between \(X\) and any other graph, is called WL-dimension of \(X\). In this paper, the authors study the WL dimension of the class of finite distance-hereditary graphs. They prove that the maximum WL-dimension of a distance-hereditary graph is 2, which improves the previously known bound that says that the WL-dimension of any distance-hereditary graph is bounded above by 7 [\textit{M. Grohe} and \textit{D. Neuen}, ACM Trans. Comput. Log. 24, No. 1, Paper No. 6, 31 p. (2023; Zbl 07650602)]. It is known that for any graph class \(\mathcal{F}\) for which there exists a constant \(d\) such that the WL-dimension of \(X\) is at most \(d\) for any \(X \in \mathcal{F}\), holds that the graph isomorphism problem restricted to \(\mathcal{F}\) is solved by the \(d\)-dim WL in polynomial time. Thus the result proved in this paper implies that the 2-dim WL solves the isomorphism problem in distance-hereditary graphs.