Rejilla menor en dígrafos

8

Thor Johnson, et al, en su artículo: Ancho de árbol dirigido , introdujeron una definición para la cuadrícula dirigida , y conjeturaron:Jk

Para cada entero k existe un entero N tal que cada dígrafo con un ancho de árbol N o más tiene un isomorfo menor a J k .(5.1)kNNJk

Y continuaron diciendo:

Nos hemos convencido de que es válido para los dígrafos planos, pero el caso general está abierto.(5.1)

Y estoy buscando este documento inédito (cómo demostraron la conjetura de los gráficos di-planar), o cosas relacionadas en este caso, en realidad cómo usar una cuadrícula de este tipo (quiero decir ).Jk

reference-request graph-theory co.combinatorics graph-minor Saeed
fuente
2
¿Ya contactó a los autores sobre eso? Yo también sentiría curiosidad por eso. Para mí, la afirmación "Nos hemos convencido a nosotros mismos" no implica necesariamente que tuvieran una versión completamente elaborada de su argumento.
Hermann Gruber el

Respuestas:

10

Hay una nueva preimpresión de Stephan Kreutzer y Ken-ichi Kawarabayashi, en la que aparentemente muestran que la afirmación (5.1) es cierta para todos los dígrafos.

Stephan Kreutzer y Ken-ichi Kawarabayashi: El teorema de la cuadrícula dirigida . arXiv: 1411.5681 [cs.DM]

EDITAR (16 de junio de 2015):

Una versión corta de su artículo aparece aquí:

Ken-ichi Kawarabayashi, Stephan Kreutzer. El teorema de la cuadrícula dirigida. En: Rocco A. Servedio, Ronitt Rubinfeld (eds.), Actas de la cuadragésima séptima reunión anual sobre simposio sobre teoría de la computación 2015. pp. 655-664

Hermann Gruber
fuente
8

JK

EDITAR: El documento mencionado ahora está disponible públicamente:

http://epubs.siam.org/doi/abs/10.1137/1.9781611973402.6

Johnson y col. Documento de 2001, ahora está disponible al público:

Excluyendo una cuadrícula menor en dígrafos planos

Saeed
fuente
1
Estoy interesado en conocer estos resultados. Le agradecería que proporcione las referencias recientes. ¿Recibió el borrador del documento de Seymour et al?
Chandra Chekuri
1
@ChandraChekuri, En realidad, alguien más recibió un borrador (hace muchos años), y hace unos días solo eché un vistazo al papel durante unas horas. en la primera página, uno de los principales autores escribió "No distribuir". así que no podemos esperar tenerlo, pero el nuevo resultado se publicará en SODA2013, y puedo referirme a este nuevo resultado (cuando se publique).
Saeed