Skip to main content
1 of 4

Automorphism groups of graphs of bounded treewidth

The celebrated Frucht's theorem states that every finite group is isomorphic to the automorphism group of a finite graph $G$. If we restrict $G$ to belong to a certain class, some groups may become non-representable: e.g., automorphism groups of trees are the ones obtainable from the trivial group using direct product and wreath product with symmetric groups, and groups as small as $\mathbb{Z}_3$ can be non-representable this way.

In light of this, it is natural to ask if "tree-like" graphs are inherently unable to represent all groups. One possible formulation of this to consider graphs of bounded treewidth. My questions are:

  1. Is there a large enough $k$ so that all finite groups are automorphism groups of graphs with treewidth at most $k$? If no, which growth rate of $k = k(|V|)$ is required for universal representability?
  2. Can we characterize the automorphism groups of bounded treewidth graphs for each threshold $k$ (along the lines of tree automorphism groups description above)?