5 papers
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…
Flipping and Forking
Wojciech Przybyszewski, Szymon ToruÅczyk
Monadic stability and the more general monadic dependence (or NIP) are tameness conditions for classes of logical structures, studied in the 80's in Shelah's classification program…
Separability Properties of Monadically Dependent Graph Classes
Ãdouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis +5
A graph class is monadically dependent if one cannot interpret all graphs in colored graphs from using a fixed first-order interpretation. We prove that m…
Flipper games for monadically stable graph classes
Jakub Gajarský, Nikolas Mählmann, Rose McCarty +6
A class of graphs is monadically stable if for any unary expansion of , one cannot interpret, in first-order logic, arbitrarily l…
Low rank MSO
MikoÅaj BojaÅczyk, MichaÅ Pilipczuk, Wojciech Przybyszewski +2
We introduce a new logic for describing properties of graphs, which we call low rank MSO. This is the fragment of monadic second-order logic in which set quantification is restrict…