| Line 5: | Line 5: | ||
---- | ---- | ||
| − | The Four-Color problem | + | '''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. | 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. | 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. | ||
Revision as of 12:06, 16 April 2012
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.
Cayley
Kepme
Idea of Kempe’s proof
Kempe used an argument known as the method of Kempe chains. If we have a map in which every region is colored red, green, blue or yellow except one, say X. If this final region X is not surrounded by regions of all four colors there is a color left for X.
Hence suppose that regions of all four colors surround X.
If X is surrounded by regions A, B, C, D in order, colored red, yellow, green and blue then there are two cases to consider. (i) There is no chain of adjacent regions from A to C alternately colored red and green. (ii) There is a chain of adjacent regions from A to C alternately colored red and green. If (i) holds there is no problem. Change A to green, and then interchange the color of the red/green regions in the chain joining A. Since C is not in the chain it remains green and there is now no red region adjacent to X. Color X red. If (ii) holds then there can be no chain of yellow/blue adjacent regions from B to D. [It could not cross the chain of red/green regions.] Hence property (i) holds for B and D and we change colors as above.
sources from [www.ic.uff.br/elavio/mini2.pdf]
