Generalización de gráficos de ancho de árbol delimitados localmente

¿Se conoce la siguiente clase de gráfico en la literatura?

La clase de gráficos está parametrizada por los enteros positivos y y contiene cada gráfico modo que para cada vértice , el subgrafo de inducido en todos los vértices a distancia como máximo de en tiene un ancho de árbol como máximo .$d$G = ( V , E ) v ∈ V G d v G $t$$G=(V,E)$$v\in V$$G$$d$$v$$G$$t$

Generaliza el concepto de ancho de árbol limitado localmente , y parece útil cuando se buscan estructuras locales en gráficos.

El concepto de explotar propiedades que posee un gráfico localmente puede llevarse aún más lejos. Dawar, Grohe y Kreutzer en Excluyendo localmente un menor clases consideradas de gráficos que excluyen a un menor nivel local y Dvorak, Kral y Thomas en Decidir propiedades de primer orden para grafos dispersos clases de gráficos que han (localmente) la expansión delimitadas considerados.

Ambas clases están subsumidas por clases de gráficas densas en ninguna parte, introducidas por Nesetril y Ossona de Méndez.

Grohe anunció esta semana en la conferencia Highlights que Grohe, Kreutzer y Siebertz. han demostrado que todas las propiedades de los gráficos definibles en la lógica de primer orden se pueden resolver en un tiempo casi lineal en clases de gráficos densamente inexistentes. Esto implica muchos resultados de trazabilidad de parámetros fijos en gráficos densos en ninguna parte, por ejemplo, para el conjunto dominante (conectado) y el núcleo de dígrafo (ambos parametrizados por el tamaño de la solución), el árbol Steiner (parametrizado por el tamaño del árbol) y la capacidad de satisfacción del circuito ( parametrizado por la profundidad del circuito y el peso de Hamming de la solución).

Esto no es exactamente lo que está pidiendo, pero está muy relacionado y, por lo tanto, podría ser interesante para usted:

El concepto de ancho de árbol local introducido en M. Frick, M.Grohe, Decidir las propiedades de primer orden de las estructuras descomponibles localmente en árboles es más general que la definición de ancho de árbol limitado localmente en el artículo de Wikipedia al que se refiere. Para cada gráfico , el ancho de árbol local de G es la función l t w G que asigna un radio r al ancho de árbol máximo de N G r ( v ) entre todos los vértices v de G , donde N G r ( $G$$G$$ltw^G$$r$$N^G_r(v)$$v$$G$ es el subgrafo de G inducido por vértices a distancia como máximo r a v . Una clase haacotado el ancho de árbol local, si existe una función f tal que l t w G ( r ) ≤ f ( r ) para cada r y cada gráfico G perteneciente a la clase.$N^G_r(v)$$G$$r$$v$$f$$ltw^G(r) \leq f(r)$$r$$G$