Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it true, that the minimum number of colors to color a map is still 4, even if the surface you draw the map upon is more complex than a sphere?

What if we have “Planar” graphs on Möbius strips or on a torus ?

share|improve this question
1  
In the first edition of Stan Wagon's "Mathematica in Action", there is some code for generating a picture of a 7-colored torus. –  J. M. Nov 17 '11 at 0:13
1  
There is an entire book on this, Topological Graph Theory by Jonathan L. Gross and Thomas W. Tucker –  Will Jagy Jan 3 '12 at 22:18

4 Answers 4

up vote 12 down vote accepted

No. The correct replacement for $4$ for all compact surfaces without boundary except the Klein bottle is given by the Ringel-Youngs theorem (formerly the Heawood conjecture): it takes $$\left\lfloor \frac{7 + \sqrt{49 - 24 \chi}}{2} \right\rfloor$$

colors except for the Klein bottle where it takes $6$, where $\chi$ is the Euler characteristic of the surface. For the torus, $\chi = 0$, so it takes $7$ colors. I don't know the answer off the top of my head for a Möbius strip.

share|improve this answer
4  
The presence of boundaries doesn't affect the answer; for the purposes of this question, a Mobius strip is the same as a projective plane. –  Gerry Myerson Nov 16 '11 at 23:13
1  
Just for the record: for the torus, the answer is 7; it's a theorem, not a conjecture. –  lhf Nov 17 '11 at 0:27
4  
Yes, the Heawood "conjecture", like Bertrand's "postulate", is actually a theorem (as Qiaochu knows). –  Gerry Myerson Nov 17 '11 at 0:57
1  
Is there any intuition for why the Klein bottle should be exceptional? –  Jason DeVito Nov 17 '11 at 3:04
1  
A good place to read about questions related to coloring graphs on surfaces (as well issues about the genus of a graph) is the book by Mohar and Thomassen, Graphs on Surfaces, John Hopkins U. Press, 2001. Chapter 4 has a discussion of Ringel and Youngs solution of the Heawood conjecture and Chapter 8 deals with coloring problems. –  Joseph Malkevitch Nov 17 '11 at 4:04

Apparently, that code for 7-coloring a torus from Wagon's book that I was speaking of in the comments is a bit old; here's an update for newer versions of Mathematica:

spiral[theta0_, theta1_, phi0_, phi1_, color_] := 
 ParametricPlot3D[{
  (4 + Cos[1/143 (144 phi + 12 theta)]) Cos[1/143 (12 phi + 144 theta)],
  (4 + Cos[1/143 (144 phi + 12 theta)]) Sin[1/143 (12 phi + 144 theta)], 
   Sin[1/143 (144 phi + 12 theta)]},
     {theta, theta0, theta1}, {phi, phi0, phi1},
  Mesh -> False, PlotStyle -> color]

Show[
     spiral[Pi/12, (21*Pi)/12, Pi/3, 2*Pi, White],
     spiral[-((3*Pi)/12), -(Pi/12), Pi/2, (13*Pi)/6, Green],
     spiral[-(Pi/12), Pi/12, Pi/3, 2*Pi, Brown],
     spiral[-(Pi/6), 0, Pi/6, Pi/3, Yellow],
     spiral[Pi/6, (23*Pi)/12, Pi/6, Pi/3, Blue],
     spiral[0, Pi/6, Pi/6, Pi/3, Purple], 
     spiral[Pi/12, (11*Pi)/6, 0, Pi/6, Red],
   Axes -> None, Boxed -> False, Lighting -> "Neutral", 
   PlotRange -> All, ViewPoint -> {2, 0.2, 1.2}]

7-colored torus map

share|improve this answer
    
yery nice example. thanks –  draks ... Nov 18 '11 at 7:02

Thanks for updating my code. I have left this torus example out of the newest edition of my book.

Slightly related: Mathematica has a database (GraphData) of 6000+ graphs. I have just gone through ALL the planar ones in that database and determined the chromatic number (typically 3 or 4). In particular I did all the polyhedra skeletons and their duals, motivated by a (Trubridge) light fixture I purchased. The main algorithm is Kempe's method, described in detail in my book (Mathematica in Action). Using ILP (integer-linear programming) is also possible on modest sized graphs to determine chromatic numbers, or edge chromatic numbers, etc. I don't know if there is anything especially interesting about the polyhedral case: among the 1100 chromatic numbers I found for such "polyhedral graphs", about 100 were 4 and 1100 were 3. For more info on any of this, contact me.

For named polyhedron graphs only the following were 4-chromatic: "IcosahedralGraph", "PentakisDodecahedralGraph", "SmallTriakisOctahedralGraph", "SnubDodecahedralGraph", "TetrahedralGraph", "TriakisIcosahedralGraph", "TriakisTetrahedralGraph".

As for relevance to the original question, I can say that my Kempe implementation is pretty fast for planar graphs, having succeeded on the graph of all 3300 counties in the US. As for the famous counterexamples, I conjecture that one can always get around them with Kempe by simply permuting the vertices and trying again if one reaches an impasse.

Stan Wagon (wagon a t macalester d o t e d u )

share|improve this answer

Though others have already given more ambitious answers, it may yet be worthwhile to explain why "pure thought" shows that the answer to the OP's question in the first paragraph must be no.

The key observation is this: every finite graph can be embedded in some subsurface of $\mathbb{R}^3$. To do this, start with a 2:1 planar immersion of the graph, i.e., a map which is locally an embedding into the plane at globally has, at worst, two edges crossing at any given point. (It is an easy exercise to prove that such things exist for any finite graph.) Now imagine the graph is the blueprint for a highway: it will be a bad idea for the highway to have self-intersections, so what do we do? Well, as in the real world, whenever the highway would cross itself, we can build an overpass, lifting one branch up into the third dimension so that it does not cross the other. In topological terms, we add a handle to the plane in which the graph is embedded. Thus we succeed in embedding the graph in a surface, which is in fact the $g$-handled torus (where $g$ is the number of planar crossings) minus a single point (because we are starting with the plane rather than the $2$-sphere).

[This argument actually proves something quantitative: we define the crossing number of a finite graph to be the minimal number of crossings in any $2:1$ planar immersion, and we define the embedding genus of a finite graph to be the minimum genus of a compact surface into which $G$ embeds (thus planar graphs are precisely those of genus zero). Then the above argument shows that the embedding genus of $G$ is less than or equal to the crossing number of $G$.]

For any $n \in \mathbb{Z}^+$, the complete graph $K_n$ has chromatic number $n$. Thus the map coloring numbers of a compact orientable surface of genus $g$ must tend to infinity with $g$. (The precise formula is given in Qiaochu's answer.) In fact, in the same 1968 paper in which they proved Heawood's Conjecture, Ringel and Youngs gave a precise formula for the embedding genus of $K_n$: for $n \geq 3$ it is $\frac{(n-3)(n-4)}{12}$. (Clearly it is $0$ for $1 \leq n \leq 4$.)

Comments:

1) I say "embedding genus" where most graph theorists say "genus". As an arithmetic geometer who encounters graphs while studying degeneration of algebraic curves, I reserve the term "genus" of a graph for what is classically called the cyclomatic number, i.e., the first Betti number of the corresponding cell complex.

2) I know less about this subject than the above answer might indicate. For instance, I found the computation of the embedding genus of $K_n$ via an internet search while writing this answer. In particular I have not read the paper of Ringel and Youngs. Anyone who wishes to add further information on this subject will be educating me first of all...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.