Propriétés fermées mineures qui sont explicitement exprimables par MSO

Ci-dessous, MSO désigne la logique monadique du second ordre des graphiques avec des quantifications de sommets et de contours.

Soit une petite famille fermée de graphes. Il découle de la théorie de graphe mineur de Robertson et Seymour que F est caractérisée par une liste finie H 1 , H 2 , . . . , H k des mineurs interdits. En d'autres termes, pour chaque graphe G , nous avons que G appartient à F si et seulement si G exclut tous les graphes H i comme mineurs.$\mathcal{F}$$\mathcal{F}$$H_1,H_2,...,H_k$$G$$G$$\mathcal{F}$$G$$H_i$

En conséquence de ce fait, nous avons une formule MSO qui est vrai sur un graphique G si et seulement si G ∈ F . Par exemple, les graphes planaires sont caractérisés par l'absence des graphes K 3 , 3 et K 5 comme mineurs, et il est donc facile d'écrire explicitement une formule MSO caractérisant les graphes planaires.$\varphi_{\mathcal{F}}$$G$$G\in \mathcal{F}$$K_{3,3}$$K_5$

Le problème est que pour de nombreuses propriétés mineures de graphiques fermés, la liste des mineurs interdits est inconnue. Ainsi, alors que nous savons qu'une formule MSO caractérisant cette famille de graphiques existe, nous ne savons peut-être pas ce qu'est cette formule.

D'un autre côté, il se peut que l'on puisse trouver une formule explicite pour une propriété donnée sans utiliser le théorème du graphe mineur. Ma question est liée à cette possibilité.

Question 1: Existe - t-il une petite famille fermée de graphiques , de sorte que l'ensemble des mineurs interdits n'est pas connu, mais une formule MSO φ caractérisant cet ensemble de graphiques est connue?$\mathcal{F}$$\varphi$

Question 2: Une formule MSO explicite connue pour caractériser certaines des propriétés suivantes?$\varphi$

1. Genre 1 (le graphique peut être intégré dans un tore) (voir MODIFIER ci-dessous)
2. Genre k pour certains fixes (voir MODIFICATION ci-dessous)$k>1$
3. k-extérieurplanarité pour certains k fixes > 1$k> 1$

J'apprécierais toute référence ou réflexion à ce sujet. N'hésitez pas à considérer d'autres propriétés fermées mineures, la liste ci-dessus n'est qu'illustrative.

Obs: Par explicite, je ne veux pas dire nécessairement petit. Il suffit de donner un argument explicite ou un algorithme montrant comment construire la formule caractérisant la propriété donnée. De même, dans le contexte de cette question, je considère qu'une famille de mineurs interdits est connue si l'on a donné un algorithme explicite construisant cette famille.

EDIT: J'ai trouvé un article d'Adler, Kreutzer, Grohe qui construit une formule caractérisant les graphiques du genre en se basant sur la formule caractérisant les graphiques du genre k-1. Cet article répond donc aux deux premiers éléments de la question 2. Par contre cela ne répond pas à la question 1 car il existe en effet un algorithme qui construit pour chaque k, la famille des mineurs interdits caractérisant les graphes du genre k (voir section 4.2). Cette famille est donc "connue" au sens de la question.$k$

J'ai eu une réponse ici impliquant des graphes au sommet, mais cela ne répond pas à la définition de ne pas avoir d'obstruction explicite donnée dans cette question: il existe un algorithme publié pour trouver l'ensemble d'obstruction, même s'il est trop lent à exécuter, donc nous ne savons pas réellement quel est l'ensemble d'obstruction.

$F$$k\ge 1$$G$$k$$F$$G$

$k$$G$$F$$_2$

• $G$
• $(i,j)$$0\le i,j<k$$G$$i$$j$
• $G$
• $F$