2
$\begingroup$

Knots can be represented by polynomials like the Jones polynomial. Is there a comparable representation for graphs? How does it work for subclasses like planar, k-regular...?

Google doesn't really help here...

Thanks

  • 3
    Googling "graph polynomial" will of course give a bunch of links about how to graph polynomials. Googling "graph theory polynomial" is much more successful.2012-12-03

2 Answers 2

3

Also check out the Tutte polynomial. It is actually a generalization of many polynomials in graph theory, including the chromatic polynomial and the Jones polynomial. It's not a "representation" of the graph, per se, but is extensively used.

  • 0
    How could I have missed this page. It was on [page 4](https://www.google.com/search?q=graph+polynomial&hl=de&safe=off&client=firefox-a&hs=ZPK&tbo=d&rls=org.mozilla:de:official&source=lnms&sa=X&ei=Aua7UL7XBMT44QTFkIDABg&ved=0CAYQ_AUoAA&biw=1787&bih=738#q=graph+polynomial&hl=de&safe=off&client=firefox-a&tbo=d&rls=org.mozilla:de:official&ei=8-q7UKHJFMnEsgbzhIG4AQ&start=30&sa=N&bav=on.2,or.r_gc.r_pw.r_qf.&fp=ca003bcddda1de26&bpcl=39314241&biw=1787&bih=738)... at least the first link to something related.2012-12-02
4

There are polynomial invariants for graphs. One of them is the characteristic polynomial of the adjacency matrix. This has been studied extensively, for example in connection with the graph isomorphism problem.