Weisfeiler-Leman on graphs of small twin-width

Irene Heinrich, Moritz Lichter, Klara Pakhomenko, Simon Raßmann

arXivarxiv/2601.05892Jan 9, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2601.05892
curl -X POST /api/v1/records/arxiv/2601.05892/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.05892/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'