History
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 denotes the number of proper colorings of with colors then one could establish the four color theorem by showing for all planar graphs . 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
Read more about this topic: Chromatic Polynomial
Famous quotes containing the word history:
“The one duty we owe to history is to rewrite it.”
—Oscar Wilde (1854–1900)
“Literary works cannot be taken over like factories, or literary forms of expression like industrial methods. Realist writing, of which history offers many widely varying examples, is likewise conditioned by the question of how, when and for what class it is made use of.”
—Bertolt Brecht (1898–1956)
“Certainly there is not the fight recorded in Concord history, at least, if in the history of America, that will bear a moment’s comparison with this, whether for the numbers engaged in it, or for the patriotism and heroism displayed.”
—Henry David Thoreau (1817–1862)