Invariants of Chromatic Graphs

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. 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.