The 4-color theorem applies when the map's adjacency graph (undirected graph whose nodes are regions and edges connect adjacent regions) is planar. This is the case for a standard map with simple regions and edges and adjacent regions must share a nonzero length of boundary. If we change the adjacency rules, making regions adjacent if their boundaries share a point, then the four color theorem does not hold. For example, we could create a map in which 5 regions meet at a central point. The adjacency graph of this map would be the complete graph on 5 vertices, which is non-planar, hence the 4-color theorem cannot be applied (and indeed fails, since 5 colors are clearly needed here). So your question devolves to this: Can a planar map whose regions have fractal boundaries induce a nonplanar adjacency graph? I do know that there exists tiling of the plane with three fractal regions, such that each pair of regions are adjacent, but there is no point at which all three regions meet. This does not induce a non-planar adjacency graph, but it does tell us that our intuitive notions of adjacency may deceive us when working with fractal regions. ----- Original Message ----- From: "Henry Baker" <hbaker1@pipeline.com> To: <ham>; "math-fun" <math-fun@mailman.xmission.com> Sent: Tuesday, March 22, 2005 12:39 PM Subject: [math-fun] 4CC/4CT
From what I recall, the 4 color theorem is first reduced to a theorem on planar graphs -- is this right?
What are the restrictions on map boundaries? Do fractal boundaries still work?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun