{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-12","reactions":{}}