An observation about graph isomorphism (GI) since you ask about powers greater than 1.
GI is polynomial time solvable for graphs with bounded eigenvalues multiplicity (the largest exponent in the factorization of your polynomial).
I suspect random graphs to have bounded multiplicities and random non-isomorphic graphs to have different polynomials.
A very extreme examples are Paley graphs:
sage: g1=graphs.PaleyGraph(37);factor(g1.characteristic_polynomial())
(x - 18) * (x^2 + x - 9)^18