Propiedades cerradas menores que son explícitamente expresables por MSO

A continuación, MSO denota la lógica monádica de segundo orden de los gráficos con cuantificaciones de conjuntos de vértices y conjuntos de bordes.

Sea una familia cerrada menor de gráficos. Se deduce de Robertson y de Seymour gráfico teoría menor que F se caracteriza por una lista finita H 1 , H 2 , . . . , H k de menores prohibidos. En otras palabras, para cada gráfico G , tenemos que G pertenece a F si y solo si G excluye todos los gráficos H i como menores.$\mathcal{F}$$\mathcal{F}$$H_1,H_2,...,H_k$$G$$G$$\mathcal{F}$$G$$H_i$

Como consecuencia de este hecho, tenemos una fórmula MSO lo cual es cierto en un gráfico G si y sólo si G ∈ F . Por ejemplo, los gráficos planos se caracterizan por la ausencia de los gráficos K 3 , 3 y K 5 como menores, y por lo tanto, es fácil escribir explícitamente una fórmula MSO que caracterice los gráficos planos.$\varphi_{\mathcal{F}}$$G$$G\in \mathcal{F}$$K_{3,3}$$K_5$

El problema es que para muchas propiedades agradables de gráficos cerrados menores, se desconoce la lista de menores prohibidos. Entonces, si bien sabemos que existe una fórmula MSO que caracteriza a esa familia de gráficos, es posible que no sepamos qué es esta fórmula.

Por otro lado, puede darse el caso de que uno pueda llegar a una fórmula explícita para una propiedad dada sin usar el teorema menor del gráfico. Mi pregunta está relacionada con esta posibilidad.

Pregunta 1: ¿Existe una familia cerrada menor de gráficos , de modo que no se conoce el conjunto de menores prohibidos, pero se conoce alguna fórmula MSO φ que caracteriza ese conjunto de gráficos?$\mathcal{F}$$\varphi$

Pregunta 2: ¿Está algunas explícitas MSO fórmula conocido para caracterizar algunas de las siguientes propiedades?$\varphi$

1. Género 1 (el gráfico se puede insertar en un toro) (ver EDITAR a continuación)
2. Género k para algunos fijos (ver EDITAR a continuación)$k>1$
3. k-externalplanarity para algunos k > 1 fijo$k> 1$

Agradecería cualquier referencia o pensamiento sobre este asunto. Por favor, siéntase libre de considerar otras propiedades cerradas menores, la lista anterior es solo ilustrativa.

Obs: Por explícito no quiero decir necesariamente pequeño. Es suficiente dar un argumento o algoritmo explícito que muestre cómo construir la fórmula que caracteriza la propiedad dada. Del mismo modo, en el contexto de esta pregunta, considero que se conoce a una familia de menores prohibidos si se ha dado un algoritmo explícito para construir esa familia.

EDITAR: Encontré un artículo de Adler, Kreutzer, Grohe que construye una fórmula que caracteriza los gráficos del género con base en los gráficos que caracterizan la fórmula del género k-1. Por lo tanto, este documento responde a los dos primeros elementos de la pregunta 2. Por otro lado, esto no responde a la pregunta 1 porque de hecho existe un algoritmo que construye para cada k, la familia de menores prohibidos que caracterizan gráficos del género k (ver sección 4.2). Por lo tanto, esta familia es "conocida" en el sentido de la pregunta.$k$

Tenía una respuesta aquí que involucra gráficos de ápice, pero falla la definición de no tener un conjunto de obstrucción explícito dado en esta pregunta: hay un algoritmo publicado para encontrar el conjunto de obstrucción, aunque es demasiado lento para ejecutarse, por lo que no sabemos realmente cuál es el conjunto de obstrucción.

$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$