There are some simple and amazing polynomial invariants of graphs, such as the chromatic polynomial, which are special cases of the Tutte-Grothendieck polynomial invariants of matroids. References:

1. Harary, F 1969 Graph Theory Addison-Wesley.
2. Peter Cameron Polynomial aspects of codes, matroids and permutation groups
3. Welsh, DJA 1976 Matroid Theory Academic Press, London.
4. Bollobás, B 1998 Modern Graph Theory Springer- Verlag, New York.

Supervisor: Professor Stephen Huggett