Id: arxiv/2607.10594 Url: https://arxiv.org/abs/2607.10594 Tags: math.CO, cs.LO Score: 0 Title: Recognizability equals CMSO-definability for graphs of rank-width at most two Domain: math.CO Source: arxiv Authors: Antonios Kalampakas Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-12 Page: https://delphi.science/r/arxiv/2607.10594 We prove that, on finite graphs of rank-width at most two, VR-recognizability and counting monadic second-order definability coincide. This advances the recognizability-versus-definability problem from bounded linear clique-width to the first nontrivial bounded rank-width level beyond the rank-width-one split-decomposition case. The proof first treats split-prime graphs. The maximal partial-tree theory of Clark and Whittle organizes the non-sequential cut-rank-two separations, while a single strong separation orients all strong equivalence classes and yields a CMSO-definable laminar family…