Showing math.COShow all
3 papers · 1 filter
math.CO2026
Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width
Antonios Kalampakas
The Weisfeiler-Leman (WL) algorithm tests graph isomorphism by assigning colours to -tuples of vertices and iteratively refining the colouring according to neighbourhood configu…
math.CO2026
Recognizability equals CMSO-definability for graphs of rank-width at most two
Antonios Kalampakas
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-defi…
math.CO2026
Split-Free Cable Expressions: Active Neighborhood Profiles and Linear Rank-Width
Antonios Kalampakas
We introduce split-free cable expressions and their sequential restriction. Live cables are vertex blocks that future operations cannot split. The main result identifies sequential…