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?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
2
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$):
-
1$\begingroup$ 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! $\endgroup$ – Jason DeVito Oct 6 '10 at 0:17
-
6$\begingroup$ 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. $\endgroup$ – Alon Amit Oct 6 '10 at 1:01
