coloring problems
We learned some coloring problems at the end of this semester. Graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.We have learned vertex coloring, edges coloring, the chromatic function about coloring, deletion/contraction etc. Here I want to several well-known coloring problems.
The Four-Color problem The Four-Color Conjecture was settled in the XIX century:Every map can be colored using at most four colors in such a way that adjacent regions (i.e. those sharing a common boundary segment, not just a point) receive different colors. Clearly a graph can be constructed from any map, the regions being represented by the vertices of the graph and two vertices being joined by an edge if the regions corresponding to the vertices are adjacent. The resulting graph is planar, that is, it can be drawn in the plane without any edges crossing. So, the Four-Color Conjecture asks if the vertices of a planar graph can be colored with at most 4 colors so that no two adjacent vertices use the same color.
History
The first published reference is found in Arthur Cayley’s, On the colorings of maps, Proc. Royal Geographical Society 1, 259–261, 1879. On 17 July 1879 Alfred Bray Kempe announced in Nature that he had a proof of the Four-Color
Conjecture.
Kempe was a London barrister who had studied mathematics under Cayley at Cambridge and devoted some of his time to mathematics throughout his life. At Cayley’s suggestion Kempe submitted the Theorem to the American Journal of Mathematics where it was published in the ends of 1879.
