Comment by joewalker

In Our Time (BBC R4) did a recent episode called "P vs NP" [1] which talked about graph isomorphism, and might serve as an introduction to this.

There's an MP3 download at the link. I don't think it's UK only.

[1]: http://www.bbc.co.uk/programmes/b06mtms8