MSO properties, planar graphs and minor-free graphs Courcelle's theorem states that every graph property definable in monadic second-order logic can be decided in linear time on graphs of bounded 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 : Are there any problems that are polynomially solvable on graphs of genus g but NP-hard on graphs of genus > g.
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.