<p>Being 4-colorable?  Certainly MSO, and trivial on planar graphs.  It's NP-complete for a large enough forbidden clique minor, by reduction to planar 3-colorability.</p>

CC BY-SA 3.0
2014-08-29T20:25:47.093Z
More explicitly, 4-colorability is NP-complete on the minor-closed family of apex graphs, by reduction to planar 3-colorability.
David Eppstein
CC BY-SA 3.0
2012-10-03T05:09:35.723Z
2012-10-03T05:09:35.723Z
mic
<p><a href="http://en.wikipedia.org/wiki/Courcelle%27s_theorem" rel="nofollow noreferrer">Courcelle's theorem</a> states that every graph property definable in <a href="http://en.wikipedia.org/wiki/Monadic_second-order_logic#Syntax" rel="nofollow noreferrer">monadic second-order logic</a> can be decided in linear time on graphs of bounded <a href="http://en.wikipedia.org/wiki/Treewidth" rel="nofollow noreferrer">treewidth</a>. This is one of the most well-known algorithmic meta-theorems.</p>

<p>Motivated by Courcelle's theorem, I made the following conjecture :</p>

<blockquote>
  <p><strong>Conjecture</strong> : Let $\psi$ be any MSO-definable property. If $\psi$ is solvable in polynomial-time on planar graphs, then $\psi$ is solvable in polynomial-time on all classes of minor-free graphs.</p>
</blockquote>

<p>I want to know if the above conjecture is obviously false i.e., is there an MSO-definable property that is polynomial-time solvable on planar graphs but NP-hard on some class of minor-free graphs ?</p>

<p>This is the motivation behind my <a href="https://cstheory.stackexchange.com/questions/12490/hard-problems-for-higher-genus-graphs">earlier question</a> : Are there any problems that are polynomially solvable on graphs of genus g but NP-hard on graphs of genus > g.</p>

<graph-theory><lo.logic><treewidth><planar-graphs><graph-minor>
MSO properties, planar graphs and minor-free graphs
Shiva Kintali
# MSO properties, planar graphs and minor-free graphs

(Asked by: username_0 on 2012-10-03)

[Courcelle's theorem](http://en.wikipedia.org/wiki/Courcelle%27s_theorem) states that every graph property definable in [monadic second-order logic](http://en.wikipedia.org/wiki/Monadic_second-order_logic#Syntax) can be decided in linear time on graphs of bounded [treewidth](http://en.wikipedia.org/wiki/Treewidth). This is one of the most well-known algorithmic meta-theorems.

Motivated by Courcelle's theorem, I made the following conjecture :

> **Conjecture** : Let $\psi$ be any MSO-definable property. If $\psi$ is solvable in polynomial-time on planar graphs, then $\psi$ is solvable in polynomial-time on all classes of minor-free graphs.

I want to know if the above conjecture is obviously false i.e., is there an MSO-definable property that is polynomial-time solvable on planar graphs but NP-hard on some class of minor-free graphs ?

This is the motivation behind my [earlier question](https://cstheory.stackexchange.com/questions/12490/hard-problems-for-higher-genus-graphs) : Are there any problems that are polynomially solvable on graphs of genus g but NP-hard on graphs of genus > g.

**Tags:** graph-theory, lo.logic, treewidth, planar-graphs, graph-minor

---

## 1 answers

### Answer by username_1 on 2012-10-03. Score: 18 | Accepted answer

Being 4-colorable? Certainly MSO, and trivial on planar graphs. It's NP-complete for a large enough forbidden clique minor, by reduction to planar 3-colorability.

> **Comments:**
> **username_2**: More explicitly, 4-colorability is NP-complete on the minor-closed family of apex graphs, by reduction to planar 3-colorability.  

---

