1
$\begingroup$

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 ?

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ Also, it is a very easy question, maybe it need not have been asked. $\endgroup$
    – Andrej Bauer
    Sep 7, 2010 at 23:24
  • 2
    $\begingroup$ @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. $\endgroup$
    – Mohammad Alaggan
    Sep 7, 2010 at 23:31
  • 5
    $\begingroup$ You might find Diestel's graph theory textbook (available free online) a useful reference: diestel-graph-theory.com $\endgroup$
    – András Salamon
    Sep 7, 2010 at 23:48
  • 13
    $\begingroup$ @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? $\endgroup$
    – Andrej Bauer
    Sep 8, 2010 at 8:10
  • 2
    $\begingroup$ 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. $\endgroup$
    – Robin Kothari
    Sep 8, 2010 at 14:34

3 Answers 3

Reset to default
15
$\begingroup$

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).

Improve this answer
$\endgroup$
6
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$

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