1 citations · 1 across the 3 of their papers we have counts for
3 papers · 1 filter
Treelike decompositions for transductions of sparse graphs
Jan Dreier, Jakub Gajarský, Sandra Kiefer +2
We give new decomposition theorems for classes of graphs that can be transduced in first-order logic from classes of sparse graphs -- more precisely, from classes of bounded expans…
Stable graphs of bounded twin-width
Jakub Gajarský, Michał Pilipczuk, Szymon Toruńczyk
We prove that every class of graphs that is monadically stable and has bounded twin-width can be transduced from some class with bounded sparse twin-width. This genera…
Differential games, locality and model checking for FO logic of graphs
Jakub Gajarský, Maximilian Gorsky, Stephan Kreutzer
We introduce differential games for FO logic of graphs, a variant of Ehrenfeucht-Fraïssé games in which the game is played on only one graph and the moves of both players restricte…