(New page: 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 "col...) |
|||
| Line 8: | Line 8: | ||
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 11:40, 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.
