Entender el teorema del gráfico menor

9

Esta pregunta es doble y está principalmente orientada a referencias:

  1. ¿Hay algún lugar donde se den las intuiciones principales para probar el teorema menor del gráfico, sin entrar demasiado en los detalles? Sé que la prueba es larga y difícil, pero seguramente debe haber ideas clave que puedan comunicarse de una manera más fácil.

  2. ¿Existen otras relaciones en las gráficas que puedan mostrarse como cuasi órdenes, tal vez de una manera más simple que para la relación menor? (obviamente no estoy interesado en resultados triviales aquí, como comparar tamaños). Los gráficos dirigidos también están dentro del alcance de la pregunta.

reference-request graph-theory graph-minor Denis
fuente
1
Estoy especialmente interesado en la pregunta 1 ... ¿No existe un esquema de prueba comprensible del teorema de Robertson-Seymour?
Denis

Respuestas:

8

El siguiente libro cubre algunos materiales relacionados con la demostración del teorema menor del gráfico (Capítulo 12).

Reinhard Diestel: Teoría de grafos, 4a edición, Textos de posgrado en matemáticas 173.

El autor afirma: "[...] tenemos que ser modestos: de la prueba real del teorema menor, este capítulo solo transmitirá una impresión muy aproximada. Sin embargo, como con la mayoría de los resultados verdaderamente fundamentales, la prueba ha generado el desarrollo de métodos de interés y potencial bastante independientes ".

Se puede ver una versión electrónica del libro en línea. http://diestel-graph-theory.com/

Hermann Gruber
fuente
7

Para la pregunta (2): las relaciones de subgrafo y subgrafo inducido dan lugar a cuasi órdenes en algunas clases restringidas de grafos. Una de las referencias principales es un artículo de G. Ding, Subgraphs and well-cuasi-ordering , J. Graph Theory, 16: 489–502, 1992, doi: 10.1002 / jgt.3190160509 . El papel

  1. muestra que ambos ordenamientos producen wqos en la clase de gráficos con longitudes de ruta limitadas, y
  2. Aún más interesante, caracteriza exactamente las clases hereditarias de gráficos para los cuales el ordenamiento de subgrafo se convierte en un wqo (la clase debe contener solo finitamente muchos ciclos y "gráficos H").

Se pueden encontrar más resultados en el caso del ordenamiento inducido del subgrafo en este reciente artículo de arXiv por A. Atminas, V. Lozin e I. Razgon.

Sylvain
fuente
1
El siguiente documento también podría ser de interés a este respecto: MR Fellows, D. Hermelin, FA Rosamond: Ordenes cuasi en subclases de gráficos de ancho de árbol acotado y sus aplicaciones algorítmicas. Algorithmica 64 (1): 3-18, 2012
Hermann Gruber