<p>$K_{3,3}$ is non planar and is bipartite, therefore 2-colorable. </p>

CC BY-SA 2.5
2010-09-07T23:22:49.643Z
2010-09-07T23:22:49.643Z
Suresh Venkat
<p>The Petersen Graph is 3-colorable and non-planar.</p>

CC BY-SA 2.5
2010-09-08T19:59:59.297Z
2010-09-08T19:59:59.297Z
Peter Boothe
<p>Obviously not. A graph is <a href="http://en.wikipedia.org/wiki/Bipartite_graph">bipartite</a> if and only if it is 2-colorable, but not every bipartite graph is planar (<a href="http://upload.wikimedia.org/wikipedia/commons/f/f3/Biclique_K_3_3.svg">$K_{3,3}$</a> comes to mind).</p>

CC BY-SA 2.5
2010-09-07T23:23:32.780Z
2010-09-07T23:23:32.780Z
Andrej Bauer
<p>I have been working on this thread <a href="https://cstheory.stackexchange.com/questions/791/grid-k-coloring-without-monochromatic-rectangles">Grid $k$-coloring without monochromatic rectangles</a>, and I am aware that the four color theorem implies that all planar graphs are four colorable. </p>

<p>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 ?</p>

CC BY-SA 2.5
2010-09-07T23:23:12.983Z
maybe this was accidental, but there's no need to make questions like this community wiki.
Suresh Venkat
CC BY-SA 2.5
2010-09-07T23:24:13.790Z
Also, it is a very easy question, maybe it need not have been asked.
Andrej Bauer
CC BY-SA 2.5
2010-09-07T23:25:38.140Z
Thanks for the note, I didn't find an explanation so far for the community wiki mode (even in the faq).
Mohammad Alaggan
CC BY-SA 2.5
2010-09-07T23:31:49.657Z
@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.
Mohammad Alaggan
CC BY-SA 2.5
2010-09-07T23:48:00.440Z
You might find Diestel's graph theory textbook (available free online) a useful reference: http://diestel-graph-theory.com/
András Salamon
CC BY-SA 2.5
2010-09-08T01:21:20.180Z
@András Salamon: Thanks for the useful link :).
Mohammad Alaggan
CC BY-SA 2.5
2010-09-08T08:10:28.693Z
@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?
Andrej Bauer
CC BY-SA 2.5
2010-09-08T14:34:48.603Z
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 http://math.stackexchange.com/.
Robin Kothari
<graph-theory><graph-colouring>
Is it possible to have a 4-coloring for a non-planar graph ?
Mohammad Alaggan
# Is it possible to have a 4-coloring for a non-planar graph ?

(Asked by: username_0 on 2010-09-07)

I have been working on this thread [Grid $k$-coloring without monochromatic rectangles](https://cstheory.stackexchange.com/questions/791/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 ?

**Tags:** graph-theory, graph-colouring
> **Comments:**
> **username_1**: maybe this was accidental, but there's no need to make questions like this community wiki.  
> **username_2**: Also, it is a very easy question, maybe it need not have been asked.  
> **username_0**: Thanks for the note, I didn't find an explanation so far for the community wiki mode (even in the faq).  
> **username_0**: @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.  
> **username_3**: You might find Diestel's graph theory textbook (available free online) a useful reference: http://diestel-graph-theory.com/  
> **username_0**: @András Salamon: Thanks for the useful link :).  
> **username_2**: @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?  
> **username_4**: 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 http://math.stackexchange.com/.  

---

## 3 answers

### Answer by username_2 on 2010-09-07. Score: 16 | Accepted answer

Obviously not. A graph is [bipartite](http://en.wikipedia.org/wiki/Bipartite_graph) if and only if it is 2-colorable, but not every bipartite graph is planar ([$K\_{3,3}$](http://upload.wikimedia.org/wikipedia/commons/f/f3/Biclique_K_3_3.svg) comes to mind).


---

### Answer by username_1 on 2010-09-07. Score: 6

$K\_{3,3}$ is non planar and is bipartite, therefore 2-colorable.


---

### Answer by username_5 on 2010-09-08. Score: 1

The Petersen Graph is 3-colorable and non-planar.


---

