Tell me more ×
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.
up vote 4 down vote favorite

There's a theorem that every planar graph can be colored with 4 colors in such a way that no 2 adjacent vertices have the same color. Is the opposite true as well?

share|improve this question

1 Answer

up vote 17 down vote accepted

No. Consider $K_{3,3}$, the graph with two sets of 3 vertices each such that every vertex in one set is connected to every vertex in the other. It's not planar but can be colored with just 2 colors. More generally, take any dense bipartite graph - it's still 2-colorable, but far from planar.

A picture of $K_{3,3}$ (along with $K_5$):

alt text

share|improve this answer
1  
Just for my own understanding, when you say a dense bipartite graph is "far from planar", are you making a rigorous mathematical statement? That is, can we quantify how close something is to being planar? I don't know enough graph theory to be able to tell. Thanks! – Jason DeVito Oct 6 '10 at 0:17
5  
Sure. You can consider the "crossing number" of a graph, which is just the minimal number of crossings you must have if you do insist of drawing it in the plane. There is "genus", which is the smallest number of holes in a surface in which the graph can be drawn without intersections. There are various other invariants which take the value "0" for planar graphs and can thus be considered a quantification of how non-planar a graph is. – Alon Amit Oct 6 '10 at 1:01

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.