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