CHROMATIC POLYNOMIAL

Chromatic Polynomial

Chromatic Polynomial

The chromatic polynomial of a graph is a one-variable polynomial that counts the number of ways the vertices of a graph can be properly coloured. It was invented in 1912 by G.D. Birkho in his unsuccessful attempt to solve the four-color problem. In the 1940's, Tutte generalized Birkho's polynomial by adding another variable and analyzing its combinatorial properties. The Tutte polynomial itself has been generalized to other combinatorial objects, with connections to knot theory, state changes in physics, probability and other areas. We concentrate on an extension to rooted trees where the polynomial is a complete invariant, i.e., two rooted trees T1 and T2 are isomorphic if (T1) = f (T2).

Historical introduction

How many colours are needed to colour a map so that regions sharing a border receive different colours? This problem traces its origin to Oct. 23, 1852, when Francis Guthrie asked his professor, Augustus De Morgan, whether he knew of a solution. DeMorgan, in turn, asked his friend, Sir William Rowan Hamilton, who was also stumped. This innocent question raised by a student inspired an enormous amount of research in graph theory, with a final resolution of the question occurring more than 100 years later. It's easy to see that at least four colours are necessary. For instance, in South America, note that the four countries Argentina, Brazil, Bolivia and Paraguay must all receive different colours since each pair of these countries shares a border (Christian, 2006). To prove that four colours also sue for maps in the plane (or, equivalently, on a sphere) occupied some of the best mathematicians of the 19th and 20th centuries. Instead of colouring the regions of maps, most mathematicians prefer to colour the vertices of graphs. A proper vertex colouring of a graph G is an assignment of colours to the vertices of G so that adjacent vertices receive different colours. Converting a map to a graph is straightforward: Each region of the map becomes a vertex of the graph, and two vertices of the graph are joined by an edge precisely when the corresponding regions share a boundary. Guthrie's problem can now be stated in graph-theoretic terms.

The chromatic polynomial ? (G, q) of a graph G, which was introduced by Birkhoff as the number of proper colourings of G with q colours, is one of the most mysterious but fruitful polynomials in graph theory. It is the root of many other important polynomials such as the characteristic polynomial for graded posits and the Tutte polynomial for matroids (George, 1912). Stimulated by the Four Colour Conjecture (FCC) of the time and the work of Rota et al. on the foundations of combinatory, a flood of research on such polynomials has continued for about three decades in connection with graphs, matroids, posits, and simplicial complexes, and the wave is still in its trend in connection with convexity, toric geometry, Ehrhart polynomials, and topological invariants. M-colouring of G: a mapping f between the vertices of G and the set {1, 2, ...