Showing cs.DMShow all
3 papers · 1 filter
cs.DM2018
First-order interpretations of bounded expansion classes
Jakub Gajarský, Stephan Kreutzer, Jaroslav Nešetřil +4
The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-che…
cs.DM2018
Parameterized circuit complexity of model checking first-order logic on sparse structures
Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk
We prove that for every class of graphs with effectively bounded expansion, given a first-order sentence and an -element structure whose Gaifman graph belon…
cs.DM2017
On the number of types in sparse graphs
Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk
We prove that for every class of graphs which is nowhere dense, as defined by Nesetril and Ossona de Mendez, and for every first order formula , whe…