# Planar non-3-colorable graphs

Is it true that every planar graph that is not 3-colorable has an even wheel as a subgraph? I'm asking this because I want to prove that every outerplanar graph is 3-colorable.

-
Have a look at en.wikipedia.org/wiki/Outerplanar_graph#Coloring – Gerry Myerson Dec 28 '13 at 14:33
In the comment after the bounty offer, it seems you only want someone to say definitively whether or not this is true, perhaps with a reference. [you say "I'd like to craft my own"...] Or on the other hand are you looking for an answer giving a proof or counterexample? – coffeemath Jan 1 '14 at 14:00
You mean edge coloring, since 2-connected planar graphs are 4-face-colorable and therefore have a 3-vertex-coloring... – draks ... Jan 2 '14 at 0:13
I want to prove that every outerplanar graph is 3-colorable. This is a straightforward argument if you use induction. Prove first that every vertex in an outerplanar graph has its degree $\leq 2$. Then perform induction on the number of vertices... – Benjamin Dickman Jan 2 '14 at 8:00

No.

Moral disproof: If this were true, it would be an if and only if, since it is clear that no graph with an even wheel is 3-colorable. But a graph has an even wheel as a subgraph if and only if the link of every vertex is bipartite. Checking bipartiteness can be done in polynomomial time, so checking whether a graph contains an even wheel can be done in polynomial time. But checking whether planar graphs are $3$-colorable is NP complete, so this would show P=NP.

Verification that this counterexample works: Let $W$ be the graph where we delete the squiggly edge. It has two $3$-colorings, up to permuting colors:

(I stole this from the above linked notes on NP-completeness.) In both colorings, the corners joined by the squiggly line have the same color.

It is easy to check that there is no even wheel -- $W$ is $3$-colorable, so it can't have an even wheel, then check that the new edge doesn't matter. Or just check the neighborhoods of all vertices; by symmetry, there are only 6 cases.

As Benjamin Dickman points out in comments, proving that a out-planar graph is $3$-colorable is not hard once you abandon this doomed approach.

-

This is close: http://arxiv.org/pdf/1309.7120v1.pdf

Theorem 1.2 says that every wheel-free planar graph is 3-colorable. This isn't strictly what you're after because you don't specify that the wheel has to be an induced subgraph, but might get you where you're going.

-