Automorphism groups of graphs of bounded Hadwiger number

Symmetries of combinatorial objects feature among the most intriguing combinatorial problems from both a structural and computational perspective. Indeed, the famous Graph Isomorphism Problem asks to determine the computational complexity of the decision problem whether two input graphs are isomorphic. While the problem is not known to be polynomial-time solvable, it is also known that if it were NP-complete, then the polynomial time hiearchy would collapse. The Graph Isomorphism Problem is polynomial-time equivalent to the problem of computing the automorphisms of a graph.

An old result of Frucht from the 1940s asserts that any group is the automorphism group of a graph. On the other hand, Pólya showed in the 1930s that the automorphism group of a tree must be an iterated wreath product of symmetric groups, and extending this the structure of automorphism groups of all planar graphs was fully characterised by Babai in the 1970s.

This paper concerns graphs avoiding a fixed complete graph as a minor; note that every proper minor-closed class of graphs is a subclass of the class of graphs avoiding a fixed complete graph as a minor. The authors show that the automorphism group of any such graph is obtained by repeated group extensions using abelian groups, symmetric groups and groups of bounded order. It is worth noting that previously a structural restriction on the automorphism groups was not known even for particular special instances, such as graphs with bounded tree-width or graphs embeddable in a fixed surface.