# Is it possible to have a 4-coloring for a non-planar graph ? [closed]

I have been working on this thread Grid $k$-coloring without monochromatic rectangles, and I am aware that the four color theorem implies that all planar graphs are four colorable.

The question is whether this is a necessary condition as well, i.e. whether having a proof that a graph is not planar implies it is not four colorable ?

• Also, it is a very easy question, maybe it need not have been asked. Sep 7, 2010 at 23:24
• @Andrej Bauer: I didn't formally study graph theory in fact, I am sorry if I was too ignorant not to figure it out alone. I assure you however that I have tried searching for 2 days before posting the question here and I was really stuck in the middle of my algorithm construction. Thank you however for your warm and welcoming comment. Sep 7, 2010 at 23:31
• You might find Diestel's graph theory textbook (available free online) a useful reference: diestel-graph-theory.com Sep 7, 2010 at 23:48
• @Mohammad: I apologize for my impoliteness. I thought this site is like MathOverflow, i.e., it is meant to be approximately at the level of a coffee-chat by two professionals in the area (one of which might know less than the other). Anyhow, here is how you could have answered your question: take the simplest non-planar graph, $K_3,3$ (this is on Wikipedia's article on planar graphs) and try to color it. You will succeed with two colors and answer your question. So what did you try for two days? Sep 8, 2010 at 8:10
• Yes, this site is like MO, and therefore questions are expected to be of interest to researchers in TCS. This question would have been more appropriate for math.stackexchange.com. Sep 8, 2010 at 14:34

Obviously not. A graph is bipartite if and only if it is 2-colorable, but not every bipartite graph is planar ($K_{3,3}$ comes to mind).
$K_{3,3}$ is non planar and is bipartite, therefore 2-colorable.