  A commonly studied means of parameterizing graph problems is the deletion
distance from triviality (Guo et al. 2004), which counts vertices that need to
be deleted from a graph to place it in some class for which efficient
algorithms are known. In the context of graph isomorphism, we define triviality
to mean a graph with maximum degree bounded by a constant, as such graph
classes admit polynomial-time isomorphism tests. We generalise deletion
distance to a measure we call elimination distance to triviality, based on
elimination trees or tree-depth decompositions. We establish that graph
canonisation, and thus graph isomorphism, is FPT when parameterized by
elimination distance to bounded degree, extending results of Bouland et al.
(2012).
