Menores prohibidos para gráficos de ancho de árbol acotado

Esta pregunta es similar a una de mis preguntas anteriores. Se sabe que es un menor prohibido para gráficos de ancho de árbol como máximo t .$K_{t+2}$$t$

¿Existe una familia infinita de gráficos bien parametrizados e infinitos (que no sean gráficos completos y gráficos de cuadrícula) que sean mínimos prohibidos para gráficos de cada ancho de árbol. En otras palabras, ¿existe un gráfico explícita en r vértices (que no es un gráfico completo) de modo que G r es un menor prohibido para gráficos de treewidth como máximo r , donde r es una función de t ?$G_r$$r$$G_r$$r$$r$$t$

Los conjuntos completos de menores prohibidos son conocidos por gráficos de ancho de árbol como máximo tres. Vea este artículo de Wikipedia para más detalles.

¿Se conoce el conjunto completo de menores prohibidos de gráficos de ancho de árbol como máximo cuatro?

Si G se forma a partir de un gráfico más pequeño H que no es una camarilla al agregar dos vértices x e y, de modo que x e y no sean adyacentes entre sí, sino adyacentes a todos los otros vértices de G, entonces . Porque, en cualquier descomposición árbol de G , o bien x y y tener subárboles disjuntos o tienen subárboles superpuestos. Si tienen subárboles disjuntos, todos los demás subárboles deben incluir la ruta más corta entre los árboles para x e y , de lo que se deduce que el ancho del árbol es n - $tw(G)=tw(H)+2$$G$$x$$y$$x$$y$$n-2$; la suposición de que no es una camarilla se puede usar para mostrar que n - 2 ≥ t w ( H ) + 2 . Alternativamente, si x e y tienen subárboles superpuestos, cualquier otro vértice debe tener un subárbol que toque la intersección de los dos subárboles de x e y , y podemos restringir la descomposición del árbol a esa intersección, dando una descomposición del árbol en el que x e y participar en cada nodo del árbol$H$$n-2\ge tw(H)+2$$x$$y$$x$$y$$x$$y$

Esto implica que el gráfico hiperoctaédrico con 2 k nodos es un mínimo prohibido mínimo para el ancho 2 k - 3 . Para, el gráfico octaédrico K 2 , 2 , 2 es un mínimo prohibido mínimo para el ancho tres, del cual el argumento anterior muestra que el gráfico hiperoctaédrico tiene un ancho 2 k - $K_{2,2,2,\dots}$$2k$$2k-3$$K_{2,2,2}$$2k-2$. Y si se realiza una contracción o eliminación de bordes en el gráfico hiperoctaédrico, las simetrías del gráfico nos permiten suponer que la operación está sucediendo en uno de los doce bordes en el octaedro base, causando su ancho y el ancho de todos los hiperoctaedros. construido a partir de él para disminuir.

(La otra clase de gráficos que debe incluir en su pregunta junto con los gráficos completos son los gráficos de cuadrícula. Una cuadrícula tiene un ancho de árbol r . Está separada de los gráficos menores completos porque es plana y, por lo tanto, no tiene un menor completo con más de cuatro vértices. Sin embargo, no es un mínimo prohibido mínimo, porque algunos pequeños cambios (como contraer los vértices de las esquinas) no cambian su ancho de árbol).$r\times r$$r$

$\leq 4$