Max-Cut Of Minor Closed Family
MaxCut can be solved in polynomial time in $K_5$-minor-free graphs but is NP-hard in $K_6$-minor-free graphs (in particular, for apex graphs of planar graphs) [Barahona 1983].

See also this WG 2010 paper and slides by Marcin Kamiński.