This paper investigates ultrafilters in the context of connectivity systems, defined as pairs
$(X, f) $ where $ X $ is a finite set and $ f $ is a symmetric submodular function. Ultrafilters …

We define new graph parameters, called flip-width, that generalize treewidth, degeneracy,
and generalized coloring numbers for sparse graphs, and clique-width and twin-width for …

In this survey, we review practical algorithms for graph-theoretic problems that are
expressible in monadic second-order logic. Monadic second-order (MSO) logic allows …

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 …

It is known that a number of natural graph problems which are FPT parameterized by
treewidth become W-hard when parameterized by clique-width. It is therefore desirable to …

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 define …

A conjecture in algorithmic model theory predicts that the model-checking problem for first-
order logic is fixed-parameter tractable on a hereditary graph class if and only if the class is …

We study the first-order (FO) model checking problem of dense graph classes, namely, those
that have FO interpretations in (or are FO transductions of) some sparse graph classes. We …

The recent increase of interest in the graph invariant called tree-depth and in its applications
in algorithms and logic on graphs led to a natural question: is there an analogously useful" …

Parameterized algorithms are often used to efficiently solve NP-hard problems on graphs. In
this context, vertex cover is used as a powerful parameter for dealing with graph problems …