{"id":"arxiv/2610.05263","url":"https://arxiv.org/abs/2610.05263","tags":["cs.LO","cs.DM","math.LO"],"score":0,"title":"A Logic for Minor-Free Graph Classes: Model Checking, Dependence, and Combinatorial Reconfiguration","domain":"cs.LO","source":"arxiv","authors":["Nikolas Mählmann","Patrice {Ossona de Mendez}","Nicole Schirrmacher","Sebastian Siebertz","Giannos Stamoulis","{Dimitrios M. } Thilikos","Alexandre Vigny"],"reviews":0,"subject":"cs.LO","summary":"We introduce \\emph{sub-connectivity logic}, denoted by $\\textsf{FOscon}$, an extension of first-order logic for graphs with a specified set $Z$ of admissible edges. Its additional atom $\\textsf{scon}(x,y;\\bar z)$ asserts that $x$ and $y$ are connected by a path using only edges of $Z$ and avoiding the vertices in $\\bar z$. Our main structural result states that, for every weakly sparse graph class $\\mathscr C$, the class of all expansions of graphs in $\\mathscr C$ by rooted spanning forest orders has bounded twin-width if and only if $\\mathscr C$ excludes a fixed minor. When $\\mathscr C$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-04","reactions":{}}