In the mathematical field of graph theory the chromatic polynomial for a given graph is a polynomial which encodes the number of different ways to vertex color the graph using n colors. It was first used by Birkhoff and Lewis in their attack on the four-color theorem. Mathematics, often abbreviated maths in Commonwealth English and math in American English, is the study of abstraction. ... In mathematics and computer science, graph theory studies the properties of graphs. ... In mathematics, polynomial functions, or polynomials, are an important class of simple and smooth functions. ... George David Birkhoff (21 March 1884 - 12 November 1944) was an American mathematician, and one of the most important leaders in mathematics in the USA in his generation. ... Example of a four color map The four color theorem states that every possible geographical map can be colored with at most four colors in such a way that no two adjacent regions receive the same colour. ...

It remains an unsolved problem to characterize graphs which have the same chromatic polynomial and to determine precisely what polynomials are chromatic.

Constructing the chromatic polynomial is hard and at least an NP-complete problem. In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

Definition

Let us denote by f(G,t) the number of different colorings of a labeled graph G from t colors. Two colorings of G will be considered different if at least one of the labeled points is assigned a different color.Then, it can be shown that f(G,t) will be a polynomial in t. In graph theory (which is an area in mathematics and computer science) a labeled graph is a graph with labels assigned to its nodes and edges. ... In mathematics, polynomial functions, or polynomials, are an important class of simple and smooth functions. ...

Examples

• The complete graph with 3 vertices (K₃) : f(K₃,t) = t(t − 1)(t − 2) since the first vertex can be colored in t ways, the second in t − 1 ways and so on.

• In general, a complete graph K_n with n vertices:

• A tree graph T with n vertices : f(T,t) = t(t − 1)^{n − 1}

• A circle graph C_n with n vertices : f(C_n,t) = (t − 1)ⁿ + ( − 1)ⁿ(t − 1)

In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ... In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ... A tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ... In the mathematical field of graph theory a cycle graph or circle graph is a graph that consists of a cycle. ...

Properties

• f(G,t) = 0, if t < χ(G).
• Let G be a graph with p vertices, q edges, and k components G₁,G₂,...G_k. Then:
  • f(G,t) has degree p.
  • The coefficient of t^p in f(G,t) is 1.
  • The coefficient of t^{p − 1} in f(G,t) is − q.
  • The constant term in f(G,t) is 0.
  • .
  • The smallest exponent of t in f(G,t) with a non-zero coefficient is k.
• The coefficients of every chromatic polynomial alternate in signs.
• A graph G with p vertices is a tree if and only f(G,t) = t(t − 1)^{p − 1}.