Mineurs interdits pour les graphiques à largeur d'arbre limitée

Cette question est similaire à l' une de mes précédentes. Il est connu que est un mineur interdit pour les graphiques de largeur d'arbre au plus .$K_{t+2}$$t$

Existe-t-il une famille infinie de graphiques bien paramétrés et bien construits (autres que les graphiques complets et les graphiques en grille) qui sont des mineurs minimes interdits pour les graphiques de chaque largeur d'arbre. Autrement dit, existe-t-il un graphe explicite sur sommets (qui n'est pas un graphe complet) tel que est un mineur interdit pour les graphes de largeur d'arbre au plus , où est fonction de ?$G_r$$r$$G_r$$r$$r$$t$

Les ensembles complets de mineurs interdits sont connus pour les graphiques de la largeur d'arbre au maximum trois. Voir cet article Wikipedia pour plus de détails.

Est-ce que l'ensemble complet des mineurs interdits de graphiques de largeur d'arbre au plus quatre est connu?

Si G est formé à partir d'un plus petit graphique H qui n'est pas une clique en ajoutant deux sommets x et y, de telle sorte que x et y ne soient pas adjacents mais adjacents à tous les autres sommets de G, alors . Car, dans toute décomposition arborescente de G , x et y ont des sous-arbres disjoints ou ils ont des sous-arbres qui se chevauchent. S'ils ont des sous-arbres disjoints, tous les autres sous-arbres doivent inclure le chemin le plus court entre les arbres pour x et y , d'où il résulte que la largeur de l'arbre est n - $tw(G)=tw(H)+2$$G$$x$$y$$x$$y$$n-2$; l'hypothèse que n'est pas une clique peut alors être utilisée pour montrer que n - 2 ≥ t w ( H ) + 2 . Alternativement, si x et y ont des sous-arbres qui se chevauchent, chaque autre sommet doit avoir un sous-arbre qui touche l'intersection des deux sous-arbres de x et y , et nous pouvons limiter la décomposition de l'arbre à cette intersection, donnant une décomposition d'arbre dans laquelle x et y participer à chaque nœud d'arbre.$H$$n-2\ge tw(H)+2$$x$$y$$x$$y$$x$$y$

Cela implique que le graphe hyperoctaédrique avec 2 k nœuds est un mineur minimal interdit pour la largeur 2 k - 3 . Car, le graphe octaédrique K 2 , 2 , 2 est un mineur minimal interdit pour la largeur trois, à partir duquel l'argument ci-dessus montre que le graphe hyperoctaédrique a une largeur 2 k - $K_{2,2,2,\dots}$$2k$$2k-3$$K_{2,2,2}$$2k-2$. Et si une contraction ou une suppression de bord est effectuée dans le graphique hyperoctaédrique, les symétries du graphique nous permettent de supposer que l'opération se produit sur l'un des douze bords de l'octaèdre de base, provoquant sa largeur et la largeur de tous les hyperoctaèdres construit à partir de lui pour diminuer.

(L'autre classe de graphiques que vous devriez inclure dans votre question avec les graphiques complets sont les graphiques de grille. Une grille a une largeur d'arbre r . Elle est distincte des mineurs de graphique complets car elle est plane et n'a donc pas de mineur complet avec plus de quatre sommets. Ce n'est pas un mineur minimal interdit, car certains petits changements (comme la contraction des sommets des coins) ne modifient pas la largeur de son arborescence.)$r\times r$$r$

$\leq 4$