3 papers
cs.LO2026
A Rank-Preserving Locality Theorem
Jan Dreier, Szymon ToruÅczyk
We prove a rank-preserving locality theorem for a syntactic variant of first-order logic, in the spirit of Gaifman's locality theorem and the rank-preserving locality theorem of Gr…
math.CO2026
Variants of Merge-Width and Applications
Karolina Drabik, Maël Dumas, Colin Geniet +3
Merge-width is a recently introduced family of graph parameters that unifies treewidth, clique-width, twin-width, and generalised colouring numbers. We prove the equivalence of sev…
math.CO2026
Flips and Merge-Width in Sparse Graphs
Karolina Drabik, Maël Dumas, Nikolas Mählmann +2
A flip of a graph is obtained by complementing the edge relation within a set of vertices. Flips are typically used to separate vertices in a graph, by increasing the distances bet…