Chromatic polynomial

The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to attack the four color problem. It was generalised to the Tutte polynomial by Hassler Whitney and W. T. Tutte, linking it to the Potts model of statistical physics. P ( G , x ) = P ( G − e , x ) − P ( G / e , x ) {displaystyle P(G,x)=P(G-e,x)-P(G/e,x)} , The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to attack the four color problem. It was generalised to the Tutte polynomial by Hassler Whitney and W. T. Tutte, linking it to the Potts model of statistical physics. George David Birkhoff introduced the chromatic polynomial in 1912, defining it only for planar graphs, in an attempt to prove the four color theorem. If P ( G , k ) {displaystyle P(G,k)} denotes the number of proper colorings of G with k colors then one could establish the four color theorem by showing P ( G , 4 ) > 0 {displaystyle P(G,4)>0} for all planar graphs G. In this way he hoped to apply the powerful tools of analysis and algebra for studying the roots of polynomials to the combinatorial coloring problem. Hassler Whitney generalised Birkhoff’s polynomial from the planar case to general graphs in 1932. In 1968, Read asked which polynomials are the chromatic polynomials of some graph, a question that remains open, and introduced the concept of chromatically equivalent graphs. Today, chromatic polynomials are one of the central objects of algebraic graph theory. For a graph G, P ( G , k ) {displaystyle P(G,k)} counts the number of its (proper) vertex k-colorings. Other commonly used notations include P G ( k ) {displaystyle P_{G}(k)} , χ G ( k ) {displaystyle chi _{G}(k)} , or π G ( k ) {displaystyle pi _{G}(k)} .There is a unique polynomial P ( G , x ) {displaystyle P(G,x)} which evaluated at any integer k ≥ 0 coincides with P ( G , k ) {displaystyle P(G,k)} ; it is called the chromatic polynomial of G. For example, to color the path graph P 3 {displaystyle P_{3}} on 3 vertices with k colors, one may choose any of the k colors for the first vertex, any of the k − 1 {displaystyle k-1} remaining colors for the second vertex, and lastly for the third vertex, any of the k − 1 {displaystyle k-1} colors that are different from the second vertex's choice.Therefore, P ( P 3 , k ) = k ⋅ ( k − 1 ) ⋅ ( k − 1 ) {displaystyle P(P_{3},k)=kcdot (k-1)cdot (k-1)} is the number of k-colorings of P 3 {displaystyle P_{3}} .For a variable x (not necessarily integer), we thus have P ( P 3 , x ) = x ( x − 1 ) 2 = x 3 − 2 x 2 + x {displaystyle P(P_{3},x)=x(x-1)^{2}=x^{3}-2x^{2}+x} .(Note that colorings which differ only by permuting colors or by automorphisms of G are still counted as different.) The fact that the number of k-colorings is a polynomial in k follows from a recurrence relation called the deletion–contraction recurrence or Fundamental Reduction Theorem. It is based on edge contraction: for a pair of vertices u {displaystyle u} and v {displaystyle v} the graph G / u v {displaystyle G/uv} is obtained by merging the two vertices and removing any edges between them. If u {displaystyle u} and v {displaystyle v} are adjacent in G, let G − u v {displaystyle G-uv} denote the graph obtained by removing the edge u v {displaystyle uv} .Then the numbers of k-colorings of these graphs satisfy: Equivalently, if u {displaystyle u} and v {displaystyle v} are not adjacent in G and G + u v {displaystyle G+uv} is the graph with the edge u v {displaystyle uv} added, then This follows from the observation that every k-coloring of G either gives different colors to u {displaystyle u} and v {displaystyle v} , or the same colors. In the first case this gives a (proper) k-coloring of G + u v {displaystyle G+uv} , while in the second case it gives a coloring of G / u v {displaystyle G/uv} .Conversely, every k-coloring of G can be uniquely obtained from a k-coloring of G + u v {displaystyle G+uv} or G / u v {displaystyle G/uv} (if u {displaystyle u} and v {displaystyle v} are not adjacent in G).