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.
