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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.