Recognizability equals CMSO-definability for graphs of rank-width at most two
Abstract
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 of canonical cores. Although the auxiliary partial tree is not itself transduced, it proves that every canonical local piece has a port-contiguous layout of uniformly bounded linear rank-width. The width argument uses partition atoms and the branch-width-three display theorem of Hall, Oxley, Semple, and Whittle and does not assume that graph torsos remain prime. Coherent ordered rank-two frames then permit a finite-state bottom-up evaluation whose local transitions are definable by the bounded-linear-clique-width theorem of Bojańczyk, Grohe, and Pilipczuk. Finally, the CMSO-transducible canonical split decomposition lifts the result from prime graphs to arbitrary graphs of rank-width at most two.
Related
- Diameter-two graphs whose mutual-visibility chromatic number equals their chromatic number
- A second-moment proof of quenched equals annealed for the Potts model on random regular graphs
- Power-of-two cycles in projective cubic graphs of large edge-width
- Countable Graphs with Finite Path-width: Characterisation and Universality
- Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width
BibTeX
@misc{kalampakas2026recognizability,
title = {{Recognizability equals CMSO-definability for graphs of rank-width at most two}},
author = {Antonios Kalampakas},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.10594},
eprint = {2607.10594},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.10594},
note = {CC0},
}
RIS
TY - UNPB
TI - Recognizability equals CMSO-definability for graphs of rank-width at most two
AU - Antonios Kalampakas
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2607.10594
UR - https://arxiv.org/abs/2607.10594
AB - 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 of canonical cores. Although the auxiliary partial tree is not itself transduced, it proves that every canonical local piece has a port-contiguous layout of uniformly bounded linear rank-width. The width argument uses partition atoms and the branch-width-three display theorem of Hall, Oxley, Semple, and Whittle and does not assume that graph torsos remain prime. Coherent ordered rank-two frames then permit a finite-state bottom-up evaluation whose local transitions are definable by the bounded-linear-clique-width theorem of Bojańczyk, Grohe, and Pilipczuk. Finally, the CMSO-transducible canonical split decomposition lifts the result from prime graphs to arbitrary graphs of rank-width at most two.
ER -