Properti MSO, grafik planar dan grafik minor-gratis

Teorema Courcelle menyatakan bahwa setiap properti grafik yang dapat didefinisikan dalam logika urutan kedua monadik dapat diputuskan dalam waktu linier pada grafik treewidth terikat . Ini adalah salah satu meta-teorema algoritmik yang paling terkenal.

Termotivasi oleh teorema Courcelle, saya membuat dugaan berikut:

Dugaan : Biarkan menjadi properti yang dapat didefinisikan MSO. Jika dapat dipecahkan dalam waktu polinomial pada grafik planar, maka dapat dipecahkan dalam polinomial-waktu pada semua kelas grafik bebas-minor.$\psi$$\psi$$\psi$

Saya ingin tahu apakah dugaan di atas jelas salah yaitu, adakah properti yang dapat didefinisikan-MSO yang dapat dipecahkan polinomial-waktunya pada grafik planar tetapi NP-hard pada beberapa kelas grafik bebas-kecil?

Ini adalah motivasi di balik pertanyaan saya sebelumnya : Apakah ada masalah yang secara polinomi dipecahkan pada grafik genus g tetapi NP-keras pada grafik genus> g.

Menjadi 4-warna? Tentu saja MSO, dan sepele pada grafik planar. Ini NP-lengkap untuk klik kecil terlarang yang cukup besar, dengan mengurangi ke planar 3-colorability.