4 papers
Merge-width and First-Order Model Checking
Jan Dreier, Szymon ToruÅczyk
We introduce merge-width, a family of graph parameters that unifies several structural graph measures, including treewidth, degeneracy, twin-width, clique-width, and generalized co…
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…
First-order transducibility among classes of sparse graphs
Jakub Gajarský, Jeremi GÅadkowski, Jan Jedelský +2
We prove several negative results about first-order transducibility for classes of sparse graphs: - for every , the class of graphs of treewidth at most is…
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…