3
$\begingroup$

? A graph is four colorable if and only if it is planar.

Is this true, I know that if a graph is planar it is four colorable, but is it true that if a graph is four colorable it must be a planar graph.

(EDIT) The following would have been a better way for me to have ask the question. What are the requirements for a graph to be planar? What are the requirements for a graph to be 4 colorable? Is there a simplification of the intersection of not planar and four colorable?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ No. The "utility graph" on the far left is not planar but is four colorable (in fact, two colorable): mathworld.wolfram.com/UtilityGraph.html $\endgroup$
    – Hunter Brooks
    Commented Dec 28, 2009 at 20:44
  • 11
    $\begingroup$ @unknown: I think people are downvoting your question because they feel like you didn't think about it enough before posting it. It's a fine question, but basically the very first example of a non-planar graph answers it. $\endgroup$
    – Anton Geraschenko
    Commented Dec 28, 2009 at 21:35
  • 2
    $\begingroup$ Perhaps another helpful comment: the first subdivision of any graph is two-colourable. So any topologically-defined class of graphs contains two-colourable examples. $\endgroup$
    – HJRW
    Commented Dec 28, 2009 at 22:17
  • 18
    $\begingroup$ I think the downvoting is rather harsh. The question is of interest to mathematicians and is clearly written (albeit with some misplaced punctuation). OK, so you know the answer to the question right off the top of your head? Good for you -- that's much of the point of MO. A substantial portion of the questions on this site are as obvious to someone as this is to you. Let's try to take smaller bites out of the novices... $\endgroup$
    – Pete L. Clark
    Commented Dec 28, 2009 at 22:29
  • 3
    $\begingroup$ @Pete: I'm not so sure in this case. It's very well-known that graphs are planar iff it does not have K_5 or K_3,3 as a minor, and moreover if you google "planar graph", the first hit is the wikipedia page, which contains this statement. Then it is very easy to see that K_3,3 is 2-colorable. $\endgroup$
    – Kevin H. Lin
    Commented Jan 13, 2010 at 1:58

1 Answer 1

Reset to default
12
$\begingroup$

A graph is planar if and only if it does not have $K_5$ or $K_{3,3}$ as a minor. As Hunter's comment points out, $K_{3,3}$ is bipartite, ie two-colourable.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .