On tractable parameterizations of Graph Isomorphism

Abstract. The fixed-parameter tractability of graph isomorphism is an open problem with respect to a number of natural parameters, such as tree-width, genus and maximum degree. We show that graph isomor-phism is fixed-parameter tractable when parameterized by the tree-depth of the graph. We also extend this result to a parameter generalizing both tree-depth and max-leaf-number by deploying new variants of cops-and-robbers games.