¿Teorema de la menor gráfico para gráficos dirigidos?

Question

Supongamos que $\vec{G}$ es un grafo dirigido y que $G$ es el grafo grafo obtenido a partir de $\vec{G}$ en el olvido de la dirección en cada borde. Definir $\vec{H}$ menor de edad de $\vec{G}$ si $H$ es menor de $G$ como grafo de gráficos y la dirección en los bordes de $\vec{H}$ son los mismos que los correspondientes bordes en $\vec{G}$.

¿El Robertson-Seymour Teorema de mantener para gráficos (donde la definición de menor de edad es utilizado y nuestros gráficos se permite que los bucles y varias aristas)?

Answer 1

Creo que la respuesta es sí, ver 10.5 en Neil Robertson y Paul D. Seymour. Gráfico de menores de edad. xx. wagner conjetura. Revista de Teoría Combinatoria, 92:325-357, 2004. y de la sección anterior:

Como corolario, podemos deducir el siguiente formulario de Wagner conjetura para gráficos (que implica inmediatamente la forma estándar de la conjetura para el grafo gráficos). Un grafo dirigido es un menor de otro, si el primero puede ser obtenido a partir de un subgrafo de la segunda mediante la contratación de los bordes.

10.5 Vamos $G_i$ ($i = 1,2,\ldots$) ser una contables de la secuencia de gráficos. Entonces no existe $j > i \geq 1$ tal que $G_i$ es isomorfo a un menor de $G_j$.

No he tratado de entender la prueba y no pienso probar en cualquier momento pronto. Pero estoy bastante seguro de que la definición de dígrafo menor es idéntica a su definición, y que la instrucción es exactamente el teorema que usted solicitó.

Answer 2

Jajaja Ligaduras no son bien-casi ordenó bajo contención menor. Sin embargo una subclase del dígrafo, torneo semi completo es decir (un DAG totalmente conectado), son WQO bajo contención menor. Fuente: (2011-2012) reciente papel de Seymour.