The Generalised Colouring Numbers on Classes of Bounded Expansion

摘要: The generalised colouring numbers adm_r(G), col_r(G), and wcol_r(G) were introduced by Kierstead Yang as generalisations of the usual number, also known degeneracy a graph, have since then found important applications in theory bounded expansion nowhere dense classes graphs, Nesetril Ossona de Mendez. In this paper, we study relation with two other measures that characterise namely uniform quasi-wideness, studied first Dawar et al. context preservation theorems for first-order logic, splitter game, Grohe We show every graph excluding fixed topological minor admits universal order, is, one order witnessing are small value r. Finally, use our construction such orders to give new proof result Eickmeyer Kawarabayashi, showing model-checking problem successor-invariant formulas is parameter tractable on graphs excluded minors.