  Graph polynomials are deemed useful if they give rise to algebraic
characterizations of various graph properties, and their evaluations encode
many other graph invariants. Algebraic: The complete graphs $K_n$ and the
complete bipartite graphs $K_{n,n}$ can be characterized as those graphs whose
matching polynomials satisfy a certain recurrence relations and are related to
the Hermite and Laguerre polynomials. An encoded graph invariant: The absolute
value of the chromatic polynomial $\chi(G,X)$ of a graph $G$ evaluated at $-1$
counts the number of acyclic orientations of $G$.
  In this paper we prove a general theorem on graph families which are
characterized by families of polynomials satisfying linear recurrence
relations. This gives infinitely many instances similar to the characterization
of $K_{n,n}$. We also show where to use, instead of the Hermite and Laguerre
polynomials, linear recurrence relations where the coefficients do not depend
on $n$.
  Finally, we discuss the distinctive power of graph polynomials in specific
form.
