First Order Logic and Twin-Width in Tournaments and Dense Oriented Graphs

Colin Geniet, Stéphan Thomassé

We characterise the classes of tournaments with tractable first-order model checking. For every hereditary class of tournaments $\mathcal{T}$, first-order model checking is either f…