graph polynomial

In mathematics, a graph polynomial is a graph invariant whose value is a polynomial. Invariants of this type are studied in algebraic graph theory.{{r|sdlg}}

Important graph polynomials include:

• The characteristic polynomial, based on the graph's adjacency matrix.
• The chromatic polynomial, a polynomial whose values at integer arguments give the number of colorings of the graph with that many colors.
• The dichromatic polynomial, a 2-variable generalization of the chromatic polynomial
• The flow polynomial, a polynomial whose values at integer arguments give the number of nowhere-zero flows with integer flow amounts modulo the argument.
• The (inverse of the) Ihara zeta function, defined as a product of binomial terms corresponding to certain closed walks in a graph.
• The Martin polynomial, used by Pierre Martin to study Euler tours
• The matching polynomials, several different polynomials defined as the generating function of the matchings of a graph.
• The reliability polynomial, a polynomial that describes the probability of remaining connected after independent edge failures
• The Tutte polynomial, a polynomial in two variables that can be defined (after a small change of variables) as the generating function of the numbers of connected components of induced subgraphs of the given graph, parameterized by the number of vertices in the subgraph.