Planar non-3-colorable graphs

Question

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.

Answer 1

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 some vertex is not 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.

Answer 2

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.