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