How many colors are required to color a graph?

Selam.

Today I will talk about an interesting theorem in maths. It was my homework to prepare a paper summarizing “Four Color Theorem” in high school, many years later I am doing the same thing again.

Four Color Theorem

Here is a brief summary of Four Color Theorem from Wikipedia:

The theorem states that given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Two regions are called adjacent if they share a common boundary that is not a corner, where corners are the points shared by three or more regions [1].

In 1852 a South African mathematician and botanist Francis Guthrie claimed the theorem for the first time. Then in Fallacious proofs were given independently by Alfred Kempe in 1879 and Peter Guthrie Tait in 1880. Kempe’s proof was accepted for a decade until Heawood came.

Heawood’s Formula

The following image represents Percy John Heawood’s generalized formula where γ(g) (as known as the chromatic number) is the smallest number of colors needed to color the vertices of a graph so that no two adjacent vertices share the same color. Heawood’s formula also approved Gutherie’s theorem for g=0 (g is for genus, which has a value of 0 for planar space [5]). This result was finally obtained by Appel and Haken in 1977, who constructed a computer-assisted proof that four colors were sufficient. Then a shorter, independent proof was constructed by Neil Robertson.

Heawood-Conjecture-Formula
Heawood Conjecture Formula

In December 2004, Georges Gonthier verified Appel and Hakken’s proof by representing all 1,936 possible situations of generating a map using a computer program. Initially, their proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand. Since then the proof has gained wider acceptance, although doubts remain. So, if you can find any planar map that can not be colored at least by four colors your name will be included in the chronology of this theorem. Good luck.

Featured Image

Map of provinces of Turkey can be colored using only four colors.

References

  1. http://en.wikipedia.org/wiki/Four_color_theorem
  2. http://mathworld.wolfram.com/Four-ColorTheorem.html
  3. http://mathworld.wolfram.com/HeawoodConjecture.html
  4. http://mathworld.wolfram.com/ChromaticNumber.html
  5. http://en.wikipedia.org/wiki/Genus_(mathematics)