16 citations · 94 across the 30 of their papers we have counts for
3 papers · 1 filter
Faster Existential FO Model Checking on Posets
Jakub Gajarský, Petr Hliněný, Jan Obdržálek +1
We prove that the model checking problem for the existential fragment of first-order (FO) logic on partially ordered sets is fixed-parameter tractable (FPT) with respect to the for…
Tree-depth and Vertex-minors
Petr Hliněný, O-joung Kwon, Jan Obdržálek +1
In a recent paper, Kwon and Oum claim that every graph of bounded rank-width is a pivot-minor of a graph of bounded tree-width (while the converse has been known true already befor…
Toroidal grid minors and stretch in embedded graphs
Markus Chimani, Petr Hlineny, Gelasio Salazar
We investigate the toroidal expanse of an embedded graph G, that is, the size of the largest toroidal grid contained in G as a minor. In the course of this work we introduce a new…