![]() ![]() ![]() Take the dual graph G, and remove edges and vertices to get a critical graph G′ with c(M)=c(S)=c(G)=c(G′). Start with a map M that requires the maximum number of colors for the surface S. Glad you asked! We want to know how many colors to color all maps on a surface S. So it must be the case that every vertex of K has order greater than or equal to c(K)−1. We were led to this contradiction by the assumption that K has a vertex of order less than c(K)−1. This contradicts the fact that K needs c(K) colors for a proper coloring. Do so! This means that K is now colored with c(K)−1 colors. This leaves one of the c(K)−1 colors with which to color v. Since the order of v is less than c(K)−1, the vertices joined to v have been colored with fewer than c(K)−1 colors. All you need to do is color the vertex v. Color K using the coloring you’ve already started by coloring K′. Now put the vertex v you removed back along with all the removed edges. Because K is critical, K′ can be colored in c(K)−1 or fewer colors. From the graph K remove v and all the edges joined to it. Then there must be a vertex v whose order is less than c(K)−1. ![]() This is going to be a proof by contradiction. If graph K is critical with chromatic number c(K), then every vertex of K has order at least c(K)−1. Since H was arbitrary for S k, χ H( S k) ≤ f( k). Thus e is not uniformly colored, and χ( H) ≤ f( k). Now consider an arbitrary edge e of H and any two consecutive vertices in the corresponding region of G*( H) since they form an edge of G*( H), these two vertices are colored differently. Since G*( H) ⊲ S k, χ( G*( H)) ≤ f( k), by the Heawood Map-Coloring Theorem (or the Four-Color Theorem, if k = 0) for graphs. (1) Let H ⊲ S k, and let G*( H) denote the corresponding modification of G( H). The hypergraph chromatic number of the surface S k is defined by: χ H( S k) = the maximum χ( H) such that H ⊲ S k. The latter definition holds less interest, in the following sense: replacing each edge with one complete graph reverts to the chromatic number problem for graphs. Note that this is the “weak” definition of chromatic number for hypergraphs, as we are not requiring that all vertices in an arbitrary edge be colored differently (just that they not all be colored alike.) Clearly the weak and the “strong” definitions agree, if H is a graph. That is, χ(H) is the smallest number of colors for V( H) so that no edge of H is uniformly colored. ![]()
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |