Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes

Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos

The disjoint paths logic, FOL+DP, is an extension of First-Order Logic (FOL) with the extra atomic predicate ${\mathsf{dp}}_k(x_1,y_1,\dots ,x_k,y_k),$ expressing the existence of in…