Let $G$ be a finite simple graph with nodes enumerated as $1, 2, ..., n$. Assign a variable $x_i$ to node number $i$. Consider the action of $\mathrm{Aut}\, G \subset S_n$ on the polynomial ring $$\mathbb{C}[x_1, ..., x_n],$$ where element $g \in \mathrm{Aut}\, G$ permutes variables just as it permutes nodes. By classical invariant theory the ring of invariants $$\mathbb{C}[x_1, ..., x_n]^{\mathrm{Aut}\, G}$$ is finitely generated over $\mathbb{C}$.
Question: What is an upper bound $B$ on degrees of generators of $\mathbb{C}[x_1, ..., x_n]^{\mathrm{Aut}\, G}$ in terms of $n$?
For example, if we consider graphs with $n=3$ vertices, we can enumerate all possible cases and the upper bound will turn out to be $B = 3$. If the graph is $K_3$ or has no edges, then $\mathrm{Aut}\, G = S_3$ and hence the ring of invariants is given by $$\mathbb{C}[x_1, x_2, x_3]^{S_3} = \mathbb{C}[\sigma_1, \sigma_2, \sigma_3].$$ If the graph has 1 or 2 edges, then $\mathrm{Aut}\, G = S_2$ and the ring of invariants is generated by polynomials of degree $\leq 2$.
Addendum: Note that for arbitrary subgroup of $S_n$ the upper bound is known to be $n(n-1)/2$. Hence the graph structure plays a crucial role in restricting which subgroups $\mathrm{Aut}\, G \subset S_n$ can appear.