7 citations · 8 across the 6 of their papers we have counts for
11 papers · 1 filter
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…
Nowhere dense graph classes and algorithmic applications. A tutorial at Highlights of Logic, Games and Automata 2019
Sebastian Siebertz
The notion of nowhere dense graph classes was introduced by Nešetřil and Ossona de Mendez and provides a robust concept of uniform sparseness of graph classes. Nowhere dense classe…
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…
Kernelization and approximation of distance- independent sets on nowhere dense graphs
Michał Pilipczuk, Sebastian Siebertz
For a positive integer , a distance- independent set in an undirected graph is a set of vertices pairwise at distance greater than , while a distance…
Polynomial bounds for centered colorings on proper minor-closed graph classes
Michał Pilipczuk, Sebastian Siebertz
For , a coloring of the vertices of a graph is {\em{-centered}} if for every connected subgraph~ of , either receives more than colors und…
Greedy domination on biclique-free graphs
Sebastian Siebertz
The greedy algorithm for approximating dominating sets is a simple method that is known to compute an -approximation of a minimum dominating set on any graph with ve…