First-Order Model Checking on Monadically Stable Graph Classes

Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann +3

A graph class $\mathcal{C}$ is called monadically stable if one cannot interpret, in first-order logic, arbitrary large linear orders in colored graphs from $\mathcal{C}$. We prove…