1 citations · 1 across the 3 of their papers we have counts for
4 papers
Taming graphs with no large creatures and skinny ladders
Jakub Gajarský, Lars Jaffke, Paloma T. Lima +4
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class there exists a constant such that no member of $\mathcal{G}…
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
Édouard Bonnet, Jan Dreier, Jakub Gajarský +4
We present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local cliquewidth. Notably, this includes interpret…
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…
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…