Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Have a look at en.wikipedia.org/wiki/Outerplanar_graph#Coloring –  Gerry Myerson Dec 28 '13 at 14:33
2  
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 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 at 0:13
1  
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 at 8:00

2 Answers 2

up vote 3 down vote accepted

No.

enter image description here

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:

enter image description here

(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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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