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

  • 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$ Dec 28 '09 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$ Dec 28 '09 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
    Dec 28 '09 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$ Dec 28 '09 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$ Jan 13 '10 at 1:58

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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