{"id":"arxiv/2601.05892","url":"https://arxiv.org/abs/2601.05892","tags":["math.CO","cs.DM","cs.DS"],"score":0,"title":"Weisfeiler-Leman on graphs of small twin-width","domain":"math.CO","source":"arxiv","authors":["Irene Heinrich","Moritz Lichter","Klara Pakhomenko","Simon Raßmann"],"reviews":0,"subject":"math.CO","summary":"Twin-width is a graph parameter introduced in the context of first-order model checking, and has since become a central parameter in algorithmic graph theory. While many algorithmic problems become easier on arbitrary classes of bounded twin-width, graph isomorphism on graphs of twin-width 4 and above is as hard as the general isomorphism problem. For each positive number $k$, the $k$-dimensional Weisfeiler-Leman algorithm is an iterative color refinement algorithm that encodes structural similarities and serves as a fundamental tool for distinguishing non-isomorphic graphs. We show that the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-09","reactions":{}}