Classes de graphiques avec une arborescence superconstante

Il existe plusieurs classes intéressantes de graphiques avec une largeur d'arbre bornée. Par exemple, les arbres (treewidth 1), les graphes parallèles en série (treewidth 2), les graphes planaires externes (treewidth 2), les graphes -planaires (treewidth O (k)), les graphes de branchwidth (treewidth O (k)), .. . $k$ $k$

Question: Existe-t-il des exemples de classes de graphiques intéressantes dont la largeur d'arbre n'est pas limitée par une constante, mais par une fonction à faible croissance?

Existe-t-il des classes de graphes bien connues avec une arborescence ? $O(\log\log n)$
Existe-t-il des classes de graphes bien connues avec une arborescence ? $O(\log n)$

Je serais également intéressé par les classes de graphes avec une largeur d'arbre ou où le logarithme est répété un nombre constant de fois. $O(\log^k n)$ $O(\log\log...n)$

Obs: Bien sûr, il est facile de créer des familles de graphes artificiels avec une largeur d'arbre donnée, comme la famille degrilles. Je recherche donc principalement une famille de graphes qui ont été étudiés dans d'autres branches de la théorie des graphes et qui ont une arborescence ou , mais une arborescence non constante. $\;O(\log n)\times n\;$ $O(\log n)$ $O(\log\log n)$

graph-theory treewidth Mateus de Oliveira Oliveira
la source

Les graphes libres mineurs (planar ++) ont une largeur d'arbre , de nombreuses classes de graphes ont une largeur booléenne , voir cet article: ii.uib.no/~martinv/Papers/Logarithmic_booleanwidth.pdf

O (\sqrt{(} n))

$O(\sqrt(n))$

O (\log n)

$O(\log n)$

daniello

@daniello Merci beaucoup pour votre commentaire. est toujours trop grand. Je suis vraiment intéressé par la largeur d'arbre au plus polylogarithmique. Le document sur la largeur booléenne est très intéressant et donne plusieurs belles classes avec une largeur booléenne . Mais comme la largeur booléenne est au plus égale à la largeur de clique, il existe des graphiques de largeur booléenne constante et de largeur d'arbre. Ainsi, les résultats dans l'article ne se traduisent pas immédiatement en largeur d'arbre.

\sqrt{n}

$\sqrt{n}$

O (\log n)

$O(\log n)$

\sqrt{n}

$\sqrt{n}$

Mateus de Oliveira Oliveira

Je crois que les graphiques universels pour les arbres construits par Chung et Graham 1983 ont une largeur d'arbre . Ou pour un exemple légèrement plus simple mais similaire, considérons les fermetures transitives d'arbres binaires équilibrés. $\Theta(\log n)$

Cependant, il y a aussi un résultat négatif ici. Tous les exemples que vous donnez de familles de graphiques intéressantes sont mineures fermées ou très étroitement liées aux familles mineures fermées. Mais une famille de graphes mineurs fermés contient soit tous les graphes planaires (et a donc une largeur d'arbre maximale ), soit une mineure planaire interdite (et a donc une largeur d'arbre bornée). $\Theta(\sqrt n)$

David Eppstein
la source

Classes de graphiques avec une arborescence superconstante

Réponses: