Lesson plan
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. 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.
Article summary
In mathematics, a graph polynomial is a graph invariant whose value is a polynomial. Invariants of this type are studied in algebraic graph theory. 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.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.