An observation about graph isomorphism (GI).
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