Editing Graph coloring (section)

== History ==
{{See also | History of the four color theorem | History of graph theory}}
[[File:Map of United States vivid colors shown.png|thumb|right|A map of the [[United States]] using colors to show political divisions using the [[four color theorem]].]]

The first results about graph coloring deal almost exclusively with [[planar graphs]] in the form of [[map coloring]].
While trying to color a map of the counties of England, [[Francis Guthrie]] postulated the [[four color conjecture]], noting that four colors were sufficient to color the map so that no regions sharing a common border received the same color. Guthrie's brother passed on the question to his mathematics teacher [[Augustus De Morgan]] at [[University College London|University College]], who mentioned it in a letter to [[William Rowan Hamilton|William Hamilton]] in 1852. [[Arthur Cayley]] raised the problem at a meeting of the [[London Mathematical Society]] in 1879. The same year, [[Alfred Kempe]] published a paper that claimed to establish the result, and for a decade the four color problem was considered solved. For his accomplishment Kempe was elected a Fellow of the [[Royal Society]] and later President of the London Mathematical Society.<ref>M. Kubale, ''History of graph coloring'', in {{harvtxt|Kubale|2004}}.</ref>

In 1890, [[Percy John Heawood]] pointed out that Kempe's argument was wrong. However, in that paper he proved the [[five color theorem]], saying that every planar map can be colored with no more than ''five'' colors, using ideas of Kempe. In the following century, a vast amount of work was done and theories were developed to reduce the number of colors to four,  until the four color theorem was finally proved in 1976 by [[Kenneth Appel]] and [[Wolfgang Haken]]. The proof went back to the ideas of Heawood and Kempe and largely disregarded the intervening developments.{{sfnp|van Lint|Wilson|2001|loc=Chap. 33}}
The proof of the four color theorem is noteworthy, aside from its solution of a century-old problem, for being the first major computer-aided proof.

In 1912, [[George David Birkhoff]] introduced the [[chromatic polynomial]] to study the coloring problem, which was generalised to the [[Tutte polynomial]] by [[W. T. Tutte]], both of which are important invariants in [[algebraic graph theory]]. Kempe had already drawn attention to the general, non-planar case in 1879,{{sfnp|Jensen|Toft|1995|p=2}} and many results on generalisations of planar graph coloring to surfaces of higher order followed in the early 20th century.

In 1960, [[Claude Berge]] formulated another conjecture about graph coloring, the ''strong perfect graph conjecture'', originally motivated by an [[information theory|information-theoretic]] concept called the [[zero-error capacity]] of a graph introduced by [[Claude Shannon|Shannon]]. The conjecture remained unresolved for 40 years, until it was established as the celebrated [[strong perfect graph theorem]] by [[Maria Chudnovsky|Chudnovsky]], [[Neil Robertson (mathematician)|Robertson]], [[Paul Seymour (mathematician)|Seymour]], and [[Robin Thomas (mathematician)|Thomas]] in 2002.

Graph coloring has been studied as an algorithmic problem since the early 1970s: the chromatic number problem (see section ''{{slink|#Vertex coloring}}'' below) is one of [[Karp's 21 NP-complete problems]] from 1972, and at approximately the same time various exponential-time algorithms were developed based on backtracking and on the deletion-contraction recurrence of {{harvtxt|Zykov|1949}}. One of the major applications of graph coloring,  [[register allocation]] in compilers, was introduced in 1981.