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:
“A poet’s object is not to tell what actually happened but what could or would happen either probably or inevitably.... For this reason poetry is something more scientific and serious than history, because poetry tends to give general truths while history gives particular facts.”
—Aristotle (384–323 B.C.)
“He wrote in prison, not a History of the World, like Raleigh, but an American book which I think will live longer than that. I do not know of such words, uttered under such circumstances, and so copiously withal, in Roman or English or any history.”
—Henry David Thoreau (1817–1862)
“I think that Richard Nixon will go down in history as a true folk hero, who struck a vital blow to the whole diseased concept of the revered image and gave the American virtue of irreverence and skepticism back to the people.”
—William Burroughs (b. 1914)