Continuation of part I. I intend to cover

1. applications of WQOs in algorithmic graph theory,
2. a focus on classes of graphs that are well-quasi-ordered by the induced subgraph ordering, along with Pouzet’s Conjecture,
3. the generalisation to preservation properties in first-order logic.

This will be a gentle tutorial on mostly standard results about well-quasi-orders (wqo) in a context of graph theory and algorithmic meta-theorems. I intend to cover a few basics of wqo theory, their applications in algorithmic graph theory, a focus on classes of graphs that are well-quasi-ordered by the induced subgraph ordering, along with Pouzet's Conjecture, and finally the generalisation to preservation properties in first-order logic.

.

In this tutorial we present a landscape of extensions of first-order logic (on graphs) and we discuss their expressive power and algorithmic results related to them. These extensions involve either additional predicates expressing different types of connectivity or the quantification over vertex sets that are (in a sense) of simple structure.