Technical Reports

The ICICS/CS Reading Room

UBC CS TR-88-22 Summary

Invariants of Chromatic Graphs, November 1988 Teresa Maria Przytycka and J. H. Przytycki

In the paper we construct abstract algebras which yield invariants of graphs (including graphs with colored edges --- chromatic graphs). We analyse properties of those algebras. We show that various polynomials of graphs are yielded by models of the algebras (including Tutte and matching polynomials). In particular we consider a generalization of Tutte's polynomial to a polynomial of chromatic graphs. We analyse relation of graph polynomials with recently discovered link polynomials. \n It is known that computing of the Tutte polynomial is NP-hard. We show that a part of Tutte polynomial (and its generalization) can be computed faster than in exponential time.

If you have any questions or comments regarding this page please send mail to