Généralisation des graphiques de largeur d'arbre bornés localement

La classe de graphique suivante est-elle connue dans la littérature?

La classe de graphes est paramétrée par des entiers positifs et et contient chaque graphe telle sorte que pour chaque sommet , le sous-graphe de induit sur tous les sommets à distance au plus partir de dans a une largeur d'arbre au plus .t G = ( V , E ) v $d$$t$$G=(V,E)$$v\in V$$G$$d$$v$$G$$t$

Il généralise le concept de largeur d'arbre limitée localement , et il semble utile lors de la recherche de structures locales dans les graphiques.

Le concept d'exploitation locale de propriétés qu'un graphe possède peut être poussé encore plus loin. Dawar, Grohe et Kreutzer dans Locally Excluding a Minor ont considéré des classes de graphes qui excluent localement un mineur et Dvorak, Kral et Thomas dans Deciding first-order properties for sparse graphs ont considéré des classes de graphes qui ont une expansion (localement limitée).

Ces deux classes sont subsumées par des classes de graphiques denses nulle part, introduites par Nesetril et Ossona de Mendez.

Grohe a annoncé cette semaine lors de la conférence Highlights que Grohe, Kreutzer et Siebertz. ont prouvé que toutes les propriétés des graphes définissables en logique de premier ordre peuvent être résolues en temps presque linéaire sur des classes de graphes nulle part denses. Cela implique de nombreux résultats de tractabilité à paramètres fixes sur des graphiques nulle part denses, par exemple pour l'ensemble dominant (connecté) et le noyau digraphique (tous deux paramétrés par la taille de la solution), l'arbre de Steiner (paramétré par la taille de l'arbre) et la satisfiabilité du circuit ( paramétré par la profondeur du circuit et le poids de Hamming de la solution).

Ce n'est pas exactement ce que vous demandez, mais c'est très proche et pourrait donc être intéressant pour vous:

$G$$G$$ltw^G$$r$$N^G_r(v)$$v$$G$$N^G_r(v)$$G$$r$$v$$f$$ltw^G(r) \leq f(r)$$r$$G$