89 citations · 408 across the 56 of their papers we have counts for
4 papers · 1 filter
Decomposition horizons and a characterization of stable hereditary classes of graphs
Samuel Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez +1
The notions of bounded-size and quasibounded-size decompositions with bounded treedepth base classes are central to the structural theory of graph sparsity introduced by two of the…
Rankwidth meets stability
Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk +2
We study two notions of being well-structured for classes of graphs that are inspired by classic model theory. A class of graphs is monadically stable if it is impossible to de…
Clustering powers of sparse graphs
Jaroslav Nešetřil, Patrice Ossona de Mendez, Michał Pilipczuk +1
We prove that if is a sparse graph --- it belongs to a fixed class of bounded expansion --- and is fixed, then the th power of can be par…
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…